给定一棵 n 个节点的无根树,你可以做如下操作若干次:
- 选择当前树上编号最大或最小的点,删去它和以它为一个端点的所有边,保留任意一个连通块作为操作后的树。
令 min 为树上所有节点编号的最小值,max 为树上所有节点编号的最大值,size 为树上的节点个数,则一棵树的权值为 min⋅max⋅size。求所有能通过上述操作得到的非空的树的权值和,对 232 取模。
输入格式
第一行一个正整数 T(1≤T≤105),表示数据组数。
对于每组数据:
第一行一个正整数 n(1≤n≤105)。
接下来 n−1 行,每行两个正整数 u,v(1≤u,v≤n),表示树上的一条无向边。保证正确描述了一棵树。
保证对于所有数据,n 的和不超过 105。
输出格式
对于每组数据,输出一行一个非负整数表示答案对 232 取模后的结果。
样例输入
6 3 1 2 2 3 3 1 3 2 3 7 2 1 3 1 4 1 5 1 6 5 7 6 6 2 1 3 1 4 1 5 4 6 1 9 2 1 3 2 4 3 5 1 6 4 7 5 8 2 9 3 9 2 1 3 2 4 3 5 4 6 5 7 2 8 3 9 5
样例输出
39 35 528 221 1145 1919
子任务
子任务编号 | 特殊性质 | 分值 |
---|---|---|
1 | n≤10 | 5 |
2 | n≤20 | 10 |
3 | n≤100 | 10 |
4 | n≤2000 | 15 |
5 | n≤3×104 | 15 |
6 | 给定的树中,每个节点的度数 ≤2 | 20 |
7 | 无 | 25 |