A16685. SubMST
编程题
省选/NOI-
知识点
题目描述
给定一棵无向无权树 $T$，包含 $n$ 个顶点。
定义一个完全无向加权图 $G$，有 $n$ 个顶点，其中 $G$ 中顶点 $u$ 和 $v$ 之间的边的权值等于原树中 $u$ 到 $v$ 的距离。
对于所有可能的顶点子集，考虑由这些顶点诱导出的 $G$ 的子图的最小生成树（MST）。计算所有可能顶点子集的 MST 权值之和。
由于答案可能很大，只需输出结果对 $10^9 + 7$ 取模后的值。
定义一个完全无向加权图 $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$。
每组测试数据第一行包含一个整数 $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
说明/提示
第一个测试用例如图所示。仅包含至多一个顶点的子集未予展示，因为这些子集的权值为 $0$，对答案没有贡献。
