Дано дерево с \(n\) вершинами. Каждую вершину дерева вы можете раскрасить в \(0\) или \(1\).
Значение пути \((u,v)\) равно MEX\(^\dagger\) цветов вершин на кратчайшем пути между \(u\) и \(v\).
Значение раскраски равно сумме значений всех путей \((u,v)\) таких, что \(1 \leq u \leq v \leq n\).
Чему равно максимально возможное значение раскраски дерева?
\(^{\dagger}\) MEX (minimum excluded) массива — это наименьшее неотрицательное целое число, которое не принадлежит массиву.
Например:
- MEX \([2,2,1]\) равно \(0\), потому что \(0\) не принадлежит массиву.
- MEX \([3,1,0,1]\) равно \(2\), потому что \(0\) и \(1\) принадлежат массиву, но \(2\) нет.
- MEX \([0,3,1,2]\) равно \(4\), потому что \(0\), \(1\), \(2\) и \(3\) принадлежат массиву, но \(4\) нет.
Выходные данные
Для каждого набора входных данных выведите максимально возможное значение любой раскраски дерева.
Примечание
В первом примере мы закрасим вершину \(2\) в \(1\), а вершины \(1,3\) в \(0\). Затем мы рассмотрим все пути:
- \((1,1)\) со значением \(1\)
- \((1,2)\) со значением \(2\)
- \((1,3)\) со значением \(2\)
- \((2,2)\) со значением \(0\)
- \((2,3)\) со значением \(2\)
- \((3,3)\) со значением \(1\)
Сумма значений равна \(8\), что является максимально возможной суммой.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3
1 2
2 3
4
1 2
1 3
1 4
10
1 2
1 3
3 4
3 5
1 6
5 7
2 8
6 9
6 10
1
|
8
15
96
1
|