D. Дерево MEX
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дано дерево с $$$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$$$ нет.
Входные данные

Каждый тест содержит несколько наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество вершин в дереве.

Следующие $$$n-1$$$ строк каждого набора содержат $$$2$$$ целых числа $$$a_i$$$ и $$$b_i$$$ ($$$1 \leq a_i, b_i \leq n, a_i \neq b_i$$$) — ребро между вершинами $$$a_i$$$ и $$$b_i$$$. Гарантируется, что заданные ребра образуют дерево.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите максимально возможное значение любой раскраски дерева.

Пример
Входные данные
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
Примечание

В первом примере мы закрасим вершину $$$2$$$ в $$$1$$$, а вершины $$$1,3$$$ в $$$0$$$. Затем мы рассмотрим все пути:

  • $$$(1,1)$$$ со значением $$$1$$$
  • $$$(1,2)$$$ со значением $$$2$$$
  • $$$(1,3)$$$ со значением $$$2$$$
  • $$$(2,2)$$$ со значением $$$0$$$
  • $$$(2,3)$$$ со значением $$$2$$$
  • $$$(3,3)$$$ со значением $$$1$$$

Сумма значений равна $$$8$$$, что является максимально возможной суммой.