P14888 Pair Counting

给定一棵包含 $n$ 个结点的无根树。 初始时，你需要确定一个结点为根；接下来，你可以进行任意次操作。 每次操作，你需要依次执行下面的步骤： - 选择一个正整数 $k$。 - 标记当前每一棵树中到其根距离为 $k$ 的结点，删掉这些结点与其父亲的连边，形成若干棵新树。 - 令这些被标记的结点为对应新树的根。 其中，点 $u$ 到点 $v$ 的距离等于两点之间简单路径上边的数量。 对于点对 $(x,y)$，如果有一种钦定根与操作的方案，能使得结点 $x$ 与结点 $y$ 在同一次操作中被标记，我们称该二元组是**优美的**。 你需要求出满足 $1\le x

**本题有多组测试数据。** 输入的第一行一个整数 $T$ 表示测试数据组数（$1\le T\le 10^5$）。 对于每组测试数据， - 第一行包含一个整数 $n$（$3\le n\le 10^6$）。 - 接下来 $n−1$ 行，第 $i$ 行包含两个整数 $u_i,v_i$，表示树上编号为 $i$ 的边连接结点 $u_i$ 和 $v_i$。 保证给出的所有边构成一棵树；保证对于单个测试点，所有 $n$ 的和不超过 $10^6$。

对于每组测试数据，输出一行一个整数表示答案。

#### 样例解释 对于第一组数据，优美的点对只有 $(1,3)$。 对于第二组数据，优美的点对有 $(1,3)$、$(1,4)$ 和 $(3,4)$。