E. Находчивая гусеничная последовательность
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Endless Repeating 7 Days
— r-906, Panopticon

Дано дерево, состоящее из $$$n$$$ вершин. Гусеница обозначается парой целых чисел $$$(p, q)$$$ ($$$1 \leq p, q \leq n$$$, $$$p \neq q$$$): её голова находится в вершине $$$p$$$, её хвост находится в вершине $$$q$$$, и она доминирует над всеми вершинами на простом пути от $$$p$$$ до $$$q$$$ (включая $$$p$$$ и $$$q$$$). Гусеничная последовательность пары $$$(p, q)$$$ определяется как последовательность, состоящая только из вершин на простом пути, отсортированных в порядке возрастания расстояния до $$$p$$$.

Нора и Арон по очереди двигают гусеницу, причем Нора ходит первой. Оба игрока будут использовать свою собственную оптимальную стратегию:

  • Они будут играть, чтобы выиграть;
  • Однако, если это невозможно, они будут играть, чтобы помешать другому человеку победить (таким образом, игра закончится ничьёй).

В свой ход Нора может выбрать вершину $$$u$$$, смежную с вершиной $$$p$$$, над которой не доминирует гусеница, и переместить все вершины в ней на одно ребро по направлению к вершине $$$u$$$$$$^{\text{∗}}$$$. В свою очередь, Арон может выбрать вершину $$$v$$$, смежную с вершиной $$$q$$$, над которой не доминирует гусеница, и переместить все вершины в ней на одно ребро по направлению к вершине $$$v$$$. Обратите внимание, что ходы, разрешенные двум игрокам, различны.

Если $$$p$$$ — лист$$$^{\text{†}}$$$, то Нора выигрывает$$$^{\text{‡}}$$$. Если $$$q$$$ — лист, то Арон выигрывает. Если либо изначально оба $$$p$$$ и $$$q$$$ являются листьями, либо после $$$10^{100}$$$ ходов игра не закончится, результатом будет ничья.

Пожалуйста, посчитайте количество целочисленных пар $$$(p, q)$$$ с $$$1 \leq p, q \leq n$$$ и $$$p \neq q$$$ таких, что если изначально гусеница находится на $$$(p, q)$$$, то Арон выиграет.

$$$^{\text{∗}}$$$Другими словами: Пусть текущая гусеничная последовательность равна $$$c_1, c_2, \ldots, c_k$$$. Тогда после перемещения новая гусеничная последовательность становится $$$d(u, c_1), d(u, c_2), \ldots, d(u, c_k)$$$. Здесь $$$d(x, y)$$$ обозначает следующую вершину на простом пути от $$$y$$$ до $$$x$$$.

$$$^{\text{†}}$$$В дереве вершина называется листом тогда и только тогда, когда её степень равна $$$1$$$.

$$$^{\text{‡}}$$$Поэтому Нора всегда может выбрать вершину $$$u$$$, если игра ещё не закончилась. То же самое относится и к Арону.

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

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

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

Каждая из следующих $$$n - 1$$$ строк содержит по два целых числа $$$u$$$ и $$$v$$$ ($$$1 \leq u, v \leq n$$$), обозначающих ребро между вершинами $$$u$$$ и $$$v$$$. Гарантируется, что заданные ребра образуют дерево.

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

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

Для каждого набора входных данных выведите одну строку, содержащую целое число: количество целых пар $$$(p, q)$$$, для которых Арон выиграет.

Пример
Входные данные
5
2
1 2
5
1 2
1 3
2 4
2 5
12
1 6
11 2
4 8
12 3
2 7
6 12
8 1
2 3
5 12
9 2
10 3
10
1 2
2 3
3 4
4 5
5 6
4 7
6 8
4 9
4 10
25
1 16
11 22
6 14
3 1
20 14
23 17
25 19
10 11
3 18
10 6
2 21
4 5
11 12
4 9
9 13
8 6
6 1
3 7
8 19
10 24
15 13
1 2
3 4
17 8
Выходные данные
0
6
40
27
171
Примечание

В первом наборе входных данных всеми возможными гусеницами являются $$$(1, 2)$$$ и $$$(2, 1)$$$, что приводит к ничьей с самого начала, поскольку оба $$$p$$$ и $$$q$$$ являются листьями.

Во втором наборе входных данных, гусеницы, которые позволяют Арону выиграть, следующие: $$$(1, 3)$$$, $$$(1, 4)$$$, $$$(1, 5)$$$, $$$(2, 3)$$$, $$$(2, 4)$$$, $$$(2, 5)$$$. Давайте рассмотрим некоторых гусениц.

  • Для гусеницы $$$(1, 5)$$$: вершина $$$p = 1$$$ — это не лист, но вершина $$$q = 5$$$ — лист, так что Арон выигрывает в самом начале.
  • Для гусеницы $$$(2, 1)$$$: вершина $$$p = 2$$$ не является листом, и $$$q = 1$$$ не является листом. На первом ходу Нора может переместить гусеницу в направлении вершины $$$5$$$. Следовательно, гусеница становится $$$(5, 2)$$$, а вершина $$$p = 5$$$ — лист, так что Нора выиграет.