P12480 [集训队互测 2024] Classical Counting Problem

给定一棵 $n$ 个节点的无根树，你可以做如下操作若干次： - 选择当前树上编号最大或最小的点，删去它和以它为一个端点的所有边，保留任意一个连通块作为操作后的树。 令 $\min$ 为树上所有节点编号的最小值，$\max$ 为树上所有节点编号的最大值，$size$ 为树上的节点个数，则一棵树的权值为 $\min \cdot \max \cdot size$。求所有能通过上述操作得到的非空的树的权值和，对 $2^{32}$ 取模。

第一行一个正整数 $T (1 \leq T \leq 10^5)$，表示数据组数。 对于每组数据： 第一行一个正整数 $n (1 \leq n \leq 10^5)$。 接下来 $n - 1$ 行，每行两个正整数 $u, v (1 \leq u, v \leq n)$，表示树上的一条无向边。保证正确描述了一棵树。 保证对于所有数据，$n$ 的和不超过 $10^5$。

对于每组数据，输出一行一个非负整数表示答案对 $2^{32}$ 取模后的结果。

### 子任务 | 子任务编号 | 特殊性质 | 分值 | | :---: | :---: | :---: | | 1 | $n \leq 10$ | 5 | | 2 | $n \leq 20$ | 10 | | 3 | $n \leq 100$ | 10 | | 4 | $n \leq 2000$ | 15 | | 5 | $n \leq 3 \times 10^4$ | 15 | | 6 | 给定的树中，每个节点的度数 $\leq 2$ | 20 | | 7 | 无 | 25 |