← 返回题目
题库练习 SubMST
← 上一题 下一题 →

A16685 | SubMST

时间限制1s
内存限制256MB
通过 / 提交0/0

题目描述

给定一棵无向无权树 $T$，包含 $n$ 个顶点。

定义一个完全无向加权图 $G$，有 $n$ 个顶点，其中 $G$ 中顶点 $u$ 和 $v$ 之间的边的权值等于原树中 $u$ 到 $v$ 的距离。

对于所有可能的顶点子集，考虑由这些顶点诱导出的 $G$ 的子图的最小生成树（MST）。计算所有可能顶点子集的 MST 权值之和。

由于答案可能很大，只需输出结果对 $10^9 + 7$ 取模后的值。

输入格式

每个测试点包含多组测试数据。第一行包含测试用例个数 $t$（$1 \le t \le 10000$）。接下来是每组测试数据的描述。

每组测试数据第一行包含一个整数 $n$（$1 \leq n \leq 5000$），表示树的顶点数。

接下来的 $n-1$ 行，每行包含两个整数 $u$ 和 $v$（$1 \leq u, v \leq n$），表示树中的一条边。

保证所有测试点中 $\sum n^2 \leq 5000^2$。

输出格式

输出所有可能顶点子集的 MST 权值之和，结果对 $10^9+7$ 取模。

输入输出样例

输入 #1
5
3
1 2
2 3
7
3 1
1 2
3 5
4 5
3 6
6 7
22
4 11
9 7
3 18
19 8
16 20
5 22
13 20
15 12
2 8
12 1
17 4
6 7
1 21
10 18
7 3
20 15
14 21
18 4
8 15
22 17
11 14
1
2
2 1
输出 #1
6
496
74069416
0
1
C++ 编辑器
输入
输出