#1859. Classical Counting Problem

    ID: 1859 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1822来源:qoj.ac数据:公开样例枚举并查集

Classical Counting Problem

Classical Counting Problem

题目描述

标题: Classical Counting Problem - Problem - QOJ.ac

#9533. Classical Counting Problem

Statistics

The problem was used in the following contests:

给定一棵 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

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

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