CF2063E Triangle Tree

某日，一棵巨树在乡间生长。小 John 决定与他的童年伙伴鹰一起将其作为新家。小 John 计划用镀锌方钢在树上建造结构，但他不知道有些结构在物理上无法实现。给定一棵以节点 $1$ 为根、包含 $n$ 个节点的有根树 $^{\text{∗}}$。节点对 $(u,v)$ 被称为好对，当且仅当 $u$ 不是 $v$ 的祖先 $^{\text{†}}$ 且 $v$ 不是 $u$ 的祖先。对于任意两个节点，$\text{dist}(u,v)$ 定义为从 $u$ 到 $v$ 的唯一简单路径的边数，$\text{lca}(u,v)$ 定义为它们的[最低公共祖先](https://en.wikipedia.org/wiki/Lowest_common_ancestor)。 定义函数 $f(u,v)$ 如下： - 若 $(u,v)$ 是好对，则 $f(u,v)$ 为满足以下条件的整数 $x$ 的数量：存在一个由边长 $\text{dist}(u,\text{lca}(u,v))$、$\text{dist}(v,\text{lca}(u,v))$ 和 $x$ 构成的非退化三角形 $^{\text{‡}}$。 - 否则，$f(u,v) = 0$。 你需要计算以下值： $$\sum_{i = 1}^{n-1} \sum_{j = i+1}^n f(i,j).$$ $^{\text{∗}}$ 树是无环连通图。有根树是指定一个特殊节点为根的树。 $^{\text{†}}$ 节点 $v$ 的祖先是从 $v$ 到根的简单路径上的所有节点（包含根但不含 $v$ 自身）。根节点没有祖先。 $^{\text{‡}}$ 当边长 $a$、$b$、$c$ 满足 $a+b \gt c$、$a+c \gt b$、$b+c \gt a$ 时，三角形为非退化的。

每个测试包含多个测试用例。第一行包含测试用例数量 $t$（$1 \le t \le 10^4$）。接下来描述各个测试用例。 每个测试用例： - 第一行包含一个整数 $n$（$1 \le n \le 3 \cdot 10^5$）——树的节点数。 - 接下来 $n-1$ 行，每行包含两个整数 $u_i$ 和 $v_i$，表示连接节点 $u_i$ 和 $v_i$ 的边（$1 \le u_i, v_i \le n$，$u_i \neq v_i$）。保证输入构成一棵树。 保证所有测试用例的 $n$ 之和不超过 $3 \cdot 10^5$。

对于每个测试用例，输出一行答案。

第一个测试用例中，唯一满足 $i