33314번 - Triangle Tree 다국어

문제

One day, a giant tree grew in the countryside. Little John, with his childhood eagle, decided to make it his home. Little John will build a structure on the tree with galvanized square steel. However, little did he know, he could not build what is physically impossible.

You are given a rooted tree¹ containing $n$ vertices rooted at vertex 1ドル$. A pair of vertices $(u,v)$ is called a good pair if $u$ is not an ancestor² of $v$ and $v$ is not an ancestor of $u$. For any two vertices, $\text{dist}(u,v)$ is defined as the number of edges on the unique simple path from $u$ to $v,ドル and $\text{lca}(u,v)$ is defined as their lowest common ancestor.

A function $f(u,v)$ is defined as follows.

• If $(u,v)$ is a good pair, $f(u,v)$ is the number of distinct integer values $x$ such that there exists a non-degenerate triangle³ formed by side lengths $\text{dist}(u,\text{lca}(u,v)),ドル $\text{dist}(v,\text{lca}(u,v)),ドル and $x$.
• Otherwise, $f(u,v)$ is 0ドル$.

You need to find the following value:

$$\sum_{i = 1}^{n-1} \sum_{j = i+1}^n f(i,j).$$

¹A tree is a connected graph without cycles. A rooted tree is a tree where one vertex is special and called the root.

²An ancestor of vertex $v$ is any vertex on the simple path from $v$ to the root, including the root, but not including $v$. The root has no ancestors.

³A triangle with side lengths $a,ドル $b,ドル $c$ is non-degenerate when $a+b > c,ドル $a+c > b,ドル $b+c > a$.

입력

Each test contains multiple test cases. The first line contains the number of test cases $t$ (1ドル \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains a single integer $n$ (1ドル \le n \le 3 \cdot 10^5$).

Each of the next $n-1$ lines contains two integers $u_i$ and $v_i,ドル denoting the two vertices connected by an edge (1ドル \le u_i,v_i \le n,ドル $u_i \neq v_i$).

It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $n$ over all test cases does not exceed 3ドル \cdot 10^5$.

출력

For each test case, output the answer on a separate line.

제한

노트

On the first test case, the only good pair $(i,j)$ satisfying $i<j$ is $(2,3)$. Here, $\text{lca}(2,3)$ is 1ドル,ドル and the two distances are 1ドル$ and 1ドル$.

There is only one value of $x$ for two side lengths 1ドル$ and 1ドル,ドル which is 1ドル$. Therefore, the answer for the first test case is 1ドル$.

On the second test case, there is no good pair. Therefore, the answer for the second test case is 0ドル$.

On the third test case, the good pairs $(i,j)$ satisfying $i<j$ are as follows.

• $(2,5)$: $\text{lca}(2,5)$ is 1ドル,ドル distances are 1ドル$ and 1ドル$. There is only one possible value of $x,ドル which is 1ドル$.
• $(3,4)$: $\text{lca}(3,4)$ is 2ドル,ドル distances are 1ドル$ and 1ドル$. There is only one possible value of $x,ドル which is 1ドル$.
• $(3,5)$: $\text{lca}(3,5)$ is 1ドル,ドル distances are 2ドル$ and 1ドル$. There is only one possible value of $x,ドル which is 2ドル$.
• $(4,5)$: $\text{lca}(4,5)$ is 1ドル,ドル distances are 2ドル$ and 1ドル$. There is only one possible value of $x,ドル which is 2ドル$.

Therefore, the answer for the third test case is 1ドル+1+1+1=4$.