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$.