CF2161F.SubMST

You are given an undirected unweighted tree $T$ with $n$ vertices.

Define a complete undirected weighted graph $G$ with $n$ vertices, where the weight of the edge between vertices $u$ and $v$ in $G$ is equal to the distance between the two vertices in the original tree.

For every possible subset of vertices, consider the minimum spanning tree (MST) of the subgraph of $G$ induced by that subset of vertices. Compute the sum of the weights of the MST for all possible subsets of vertices.

As this number is big, you are only required to output the sum modulo $10^9 + 7$.

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

定义一个包含 $n$ 个顶点的完全无向带权图 $G$，其中图 $G$ 中顶点 $u$ 与 $v$ 之间的边权等于它们在原树 $T$ 中的距离。

对每一个可能的顶点子集，考虑该子集在图 $G$ 中所诱导出的子图的最小生成树（MST）。计算所有可能顶点子集对应的 MST 的权值之和。

由于该数值可能很大，你只需输出该和对 $10^9 + 7$ 取模的结果。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10000$). The description of the test cases follows.

The first line contains an integer $n$ ($1 \leq n \leq 5000$), the number of vertices in the tree.

The following $n-1$ lines contains two integers $u$ and $v$ ($1 \leq u,v \leq n$), representing an edge between vertices $u$ and $v$ in the tree.

It is guaranteed that the sum of $n^2$ over all test cases does not exceed $5000^2$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10000$）。随后是各测试用例的描述。

第一行包含一个整数 $n$（$1 \leq n \leq 5000$），表示树中顶点的数量。

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

保证所有测试用例的 $n^2$ 之和不超过 $5000^2$。

Output a single integer, the sum of the MST weights for all possible subsets of vertices, modulo $10^9+7$.

输出一个整数，即所有可能的顶点子集对应的最小生成树（MST）权重之和，对 $10^9+7$ 取模。

The first test case is illustrated below. The subsets with at most one vertex are ommited since they have a weight of $0$ and therefore do not contribute to the sum.

第一个测试用例如下图所示。由于至多包含一个顶点的子集的权重为 $0$，因此对总和无贡献，故省略不计。