CF2063E 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 $ ^{\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](https://en.wikipedia.org/wiki/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). $ $

$ ^{\\text{∗}} $ A tree is a connected graph without cycles. A rooted tree is a tree where one vertex is special and called the root.

$ ^{\\text{†}} $ 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.

$ ^{\\text{‡}} $ 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