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)$ 定义为它们的最近公共祖先。

定义函数 $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<j$ 的好对是 $(2,3)$。此时 $\text{lca}(2,3)=1$，两个距离均为 $1$。对于边长 $1$ 和 $1$，唯一可能的 $x$ 值为 $1$，因此答案为 $1$。

第二个测试用例中没有好对，因此答案为 $0$。

第三个测试用例中，满足 $i<j$ 的好对有：

• $(2,5)$：$\text{lca}(2,5)=1$，距离为 $1$ 和 $1$，$x=1$。
• $(3,4)$：$\text{lca}(3,4)=2$，距离为 $1$ 和 $1$，$x=1$。
• $(3,5)$：$\text{lca}(3,5)=1$，距离为 $2$ 和 $1$，$x=2$。
• $(4,5)$：$\text{lca}(4,5)=1$，距离为 $2$ 和 $1$，$x=2$。
  因此答案为 $1+1+1+1=4$。

翻译由 DeepSeek R1 完成