E. Треугольное дерево
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Однажды в деревне выросло гигантское дерево. Маленький Джон, со своим детским орлом, решил сделать его своим домом. Маленький Джон построит конструкцию на дереве из оцинкованной квадратной стали. Однако он не знал, что не сможет построить то, что физически невозможно.

Вам дано корневое дерево$$$^{\text{∗}}$$$, содержащее $$$n$$$ вершин, с корнем в вершине $$$1$$$. Пара вершин $$$(u,v)$$$ называется хорошей парой, если $$$u$$$ не является предком$$$^{\text{†}}$$$ $$$v$$$, и $$$v$$$ не является предком $$$u$$$. Для любых двух вершин $$$\text{dist}(u,v)$$$ определяется как количество рёбер на уникальном простом пути от $$$u$$$ до $$$v$$$, а $$$\text{lca}(u,v)$$$ определяется как их наименьший общий предок.

Функция $$$f(u,v)$$$ определяется следующим образом.

  • Если $$$(u,v)$$$ — это хорошая пара, то $$$f(u,v)$$$ — это количество различных целых значений $$$x$$$, таких что существует невырожденный треугольник$$$^{\text{‡}}$$$ с длинами сторон $$$\text{dist}(u,\text{lca}(u,v))$$$, $$$\text{dist}(v,\text{lca}(u,v))$$$ и $$$x$$$.
  • В противном случае $$$f(u,v)$$$ равно $$$0$$$.

Вам необходимо посчитать следующее значение: $$$$$$\sum_{i = 1}^{n-1} \sum_{j = i+1}^n f(i,j).$$$$$$

$$$^{\text{∗}}$$$Деревом называется связный граф без циклов. Корневым деревом называется дерево, в котором одна из вершин специальная и называется корнем.

$$$^{\text{†}}$$$Предком вершины $$$v$$$ называется любая вершина на пути от $$$v$$$ до корня, включая корень, но не включая $$$v$$$. У корня нет предков.

$$$^{\text{‡}}$$$Треугольник с длинами сторон $$$a$$$, $$$b$$$, $$$c$$$ является невырожденным, если $$$a+b > c$$$, $$$a+c > b$$$, $$$b+c > a$$$.

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

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

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

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

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

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

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

Пример
Входные данные
4
3
1 2
1 3
3
1 2
3 2
5
2 3
1 5
4 2
1 2
11
2 1
2 3
2 4
4 5
6 5
5 7
4 8
8 9
7 10
10 11
Выходные данные
1
0
4
29
Примечание

В первом наборе входных данных единственной хорошей парой $$$(i,j)$$$, удовлетворяющей $$$i<j$$$, является $$$(2,3)$$$. Здесь $$$\text{lca}(2,3)$$$ равен $$$1$$$, а два расстояния равны $$$1$$$ и $$$1$$$.

Существует только одно значение $$$x$$$ для двух длин сторон $$$1$$$ и $$$1$$$, а именно $$$1$$$. Поэтому ответ для первого набора входных данных равен $$$1$$$.

Во втором примере нет хорошей пары. Поэтому ответ для второго теста равен $$$0$$$.

В третьем примере хорошими парами $$$(i,j)$$$, удовлетворяющими $$$i<j$$$, являются следующие:

  • $$$(2,5)$$$: $$$\text{lca}(2,5)$$$ равен $$$1$$$, расстояния равны $$$1$$$ и $$$1$$$. Существует только одно возможное значение $$$x$$$, а именно $$$1$$$.
  • $$$(3,4)$$$: $$$\text{lca}(3,4)$$$ равен $$$2$$$, расстояния равны $$$1$$$ и $$$1$$$. Существует только одно возможное значение $$$x$$$, а именно $$$1$$$.
  • $$$(3,5)$$$: $$$\text{lca}(3,5)$$$ равен $$$1$$$, расстояния равны $$$2$$$ и $$$1$$$. Существует только одно возможное значение $$$x$$$, а именно $$$2$$$.
  • $$$(4,5)$$$: $$$\text{lca}(4,5)$$$ равен $$$1$$$, расстояния равны $$$2$$$ и $$$1$$$. Существует только одно возможное значение $$$x$$$, а именно $$$2$$$.

Поэтому ответ для третьего примера равен $$$1+1+1+1=4$$$.