Triangle Tree
Contest: Codeforces Round 1000 (Div. 2)
Difficulty rating: 2300
Tags: data structures, dfs and similar, dp, greedy, trees

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$$$^{\text{∗}}$$$ containing $$$n$$$ vertices rooted at vertex $$$1$$$. A pair of vertices $$$(u,v)$$$ is called a good pair if $$$u$$$ is not an ancestor$$$^{\text{†}}$$$ 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$$$^{\text{‡}}$$$ 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).$$$$$$

Input format:
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$$$.

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

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

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

Example input:
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

Example output:
1
0
4
29

Editorial:
In this editorial, we will denote the depth of vertex $$$v$$$ as $$$d_v$$$, and the subtree size of vertex $$$v$$$ as $$$s_v$$$. They can be easily calculated using DFS.
Let us try to first understand what $$$f(x,y)$$$ means. If the two edge lengths are $$$a$$$ and $$$b$$$ (WLOG $$$a \le b$$$), the third edge length $$$L$$$ must satisfy $$$a+b>L$$$ and $$$a+L>b$$$. This results in the inequality $$$b-a<L<a+b$$$. There are exactly $$$2a-1$$$ values that satisfy this, from $$$b-a+1$$$ to $$$a+b-1$$$. This means, if $$$(u,v)$$$ is a good pair, the following holds.
$$$$$$f(u,v)=2 \cdot \min(\text{dist}(u,\text{lca}(u,v)),\text{dist}(v,\text{lca}(u,v)))-1$$$$$$
And of course, if $$$(u,v)$$$ is not a good pair, $$$f(u,v)=0$$$ by definition.
Naively summing this up for all pairs takes at least $$$\Theta(n^2)$$$ time. We will simplify the function $$$f(u,v)$$$ into a form that can be computed in batches easily, and provide a different summation that finds the same answer using a double counting proof. The simplified version of $$$f(u,v)$$$ is as follows:
$$$$$$\begin{split} f(u,v) & = 2 \cdot \min(\text{dist}(u,\text{lca}(u,v)),\text{dist}(v,\text{lca}(u,v)))-1 \\ & = 2 \cdot \min(d_u-d_\text{lca},d_v-d_\text{lca})-1 \\ & = 2 \cdot \min(d_u,d_v)-2 d_\text{lca} -1 \end{split}$$$$$$
So now we can consider summing up $$$2 \cdot \min(d_u,d_v)$$$ and $$$2d_\text{lca}+1$$$ separately.
For the former, consider the condition for vertex $$$u$$$ to decide the value of $$$\min(d_u,d_v)$$$. For this, $$$d_v$$$ must be no less than $$$d_u$$$, and $$$v$$$ must not be a descendant of $$$u$$$ (because then it will not be a good pair). Therefore, vertex $$$u$$$ decides $$$\min(d_u,d_v)$$$ for $$$(\#(d \ge d_u)-s_u)$$$ different vertices. $$$\#(d \ge d_u)$$$ can be computed using a suffix sum of frequency values of $$$d$$$. Thus, we will sum up $$$2 d_u \cdot (\#(d \ge d_u)-s_u)$$$ for all vertices.
This only has a very small issue; it counts pairs $$$(u,v)$$$ where $$$d_u=d_v$$$ twice. But thankfully, all of these pairs are good pairs (otherwise they would be the same vertex), and we can simply subtract the sum of $$$2k \cdot \binom{\#(d = k)}{2}$$$ over all $$$k$$$ from the last value.
For the latter, consider the condition for vertex $$$w$$$ to be the LCA of $$$u$$$ and $$$v$$$. $$$u$$$ and $$$v$$$ should be descendants of $$$w$$$ not equal to $$$w$$$, and they should not be in the same subtree under $$$w$$$ (because then there will be a lower common ancestor). Thus, given that the number of possible descendants is $$$S=s_w-1$$$, we can get the following value for one vertex $$$w$$$ in $$$\mathcal{O}(\#(\text{children}))$$$. Counting for all vertices thus takes $$$\mathcal{O}(n)$$$ time.
$$$$$$\sum_{par_u=w} {s_u(S-s_u)}$$$$$$
This also has a very slight issue; it counts $$$(u,v)$$$ and $$$(v,u)$$$ separately, so we only have to divide this value by $$$2$$$ to get the number of good pairs with vertex $$$w$$$ as LCA. Multiplying $$$2d_w+1$$$ during the summation, we get the sum of the latter value.
Thus, we have proved that the following sum yields the very same value that we need:
$$$$$$\sum_{u=1}^n{\left({2 d_u \cdot (\#(d \ge d_u)-s_u)}\right)}-\sum_{k=0}^{n-1}{\left({2k \cdot \binom{\#(d = k)}{2}}\right)}-\frac{1}{2}\sum_{w=1}^n {\left({(2d_w+1) \cdot \sum_{par_u=w}{s_u(s_w-1-s_u)}}\right)}$$$$$$
Everything in this summation is in a form that can be computed in $$$\mathcal{O}(n)$$$ total time. Therefore, we have solved the problem with time complexity $$$\mathcal{O}(n)$$$.