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$^1$ with $n$ vertices, rooted at vertex $1$. A pair of vertices $(u,v)$ is called a good pair if $u$ is not an ancestor$^2$ of $v$ and $v$ is not an ancestor of $u$. For any two vertices, $\text{dist}(u,v)$ is the number of edges on the unique simple path from $u$ to $v$, and $\text{lca}(u,v)$ is their lowest common ancestor.

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

• If $(u,v)$ is a good pair, $f(u,v)$ is the number of distinct integers $x$ for which a non-degenerate triangle$^3$ exists with side lengths $\text{dist}(u,\text{lca}(u,v))$, $\text{dist}(v,\text{lca}(u,v))$, and $x$.
• Otherwise, $f(u,v)=0$.

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

1 A tree is a connected graph without cycles. A rooted tree is a tree in which one vertex is designated as the root.

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

3 A triangle with side lengths $a$, $b$, $c$ is non-degenerate when $a+b>c$, $a+c>b$, and $b+c>a$.

The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). Each test case is given as 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$ ($1 \le u_i,v_i \le n$, $u_i \neq v_i$), the two vertices joined by an edge. The given edges form a tree.

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.

In the first test case, the only good pair with $i<j$ is $(2,3)$. Here $\text{lca}(2,3)$ is $1$, and both distances are $1$. For side lengths $1$ and $1$, the only valid $x$ is $1$, so the answer for the first test case is $1$.

The second test case has no good pair, so the answer is $0$.

In the third test case, the good pairs with $i<j$ are the following.

• $(2,5)$: $\text{lca}(2,5)$ is $1$, and the distances are $1$ and $1$. The only possible $x$ is $1$.
• $(3,4)$: $\text{lca}(3,4)$ is $2$, and the distances are $1$ and $1$. The only possible $x$ is $1$.
• $(3,5)$: $\text{lca}(3,5)$ is $1$, and the distances are $2$ and $1$. The only possible $x$ is $2$.
• $(4,5)$: $\text{lca}(4,5)$ is $1$, and the distances are $2$ and $1$. The only possible $x$ is $2$.

So the answer for the third test case is $1+1+1+1=4$.