有一天,乡村里长出了一棵巨树。小约翰和他儿时的老鹰决定把这里当作自己的家。小约翰将用镀锌方钢在树上建造一个结构。然而,他几乎不知道,他无法建造物理上不可能的东西。
给你一棵有根树$$$^{\text{*}}$$$,其中包含$$$n$$$个顶点,以顶点$$$1$$$为根。如果 $$$u$$$ 不是 $$$v$$$ 的祖先$$$^{\text{†}}$$$ 且 $$$v$$$ 不是 $$$u$$$ 的祖先,则一对顶点 $$$(u,v)$$$ 被称为好对。对于任意两个顶点, $$$\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{‡}}$$$, $$$\text{dist}(v,\text{lca}(u,v))$$$ 和 $$$x$$$。
- 否则,$$$f(u,v)$$$ 是 $$$0$$$。
您需要找到以下值:$$$$$$\sum_{i = 1}^{n-1} \sum_{j = i+1}^n f(i,j).$$$$$$
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$)。
接下来的 $$$n-1$$$ 行包含两个整数 $$$u_i$$$ 和 $$$v_i$$$,表示由边连接的两个顶点 ($$$1 \le u_i,v_i \le n$$$, $$$u_i \neq v_i$$$)。
保证给定的边形成一棵树。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。
输出
对于每个测试用例,在单独的行上输出答案。
示例
输入 #1
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
输出 #1
1 0 4 29
注意
在第一个测试用例中,唯一满足 $$$i<j$$$ 的好对 $$$(i,j)$$$ 是 $$$(2,3)$$$。这里,$$$\text{lca}(2,3)$$$是$$$1$$$,两个距离是$$$1$$$和$$$1$$$。
两条边长 $$$1$$$ 和 $$$1$$$ 的 $$$x$$$ 只有一个值,即 $$$1$$$。因此,第一个测试用例的答案是$$$1$$$。
在第二个测试用例中,没有好的对。因此,第二个测试用例的答案是$$$0$$$。
在第三个测试用例中,满足 $$$i<j$$$ 的好对 $$$(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$$$。