F - 被包围的节点

得分：$600$ 分

问题描述

给定一棵有 $N$ 个顶点的树 $T$。第 $i$ 条边连接顶点 $A_i$ 和 $B_i$ ($1 \leq A_i,B_i \leq N$)。

然后，每个顶点以概率 $1/2$ 被涂成黑色，以概率 $1/2$ 被涂成白色，各个顶点之间的选择是独立的。那么，令 $S$ 为包含全部被涂成黑色的顶点的最小子树（连通子图）。（如果没有顶点被涂成黑色，$S$ 是空图）。

设 $S$ 中包含的白色顶点的数量为洞穴程度（holeyness）。求 $S$ 的洞穴程度期望。

由于答案是一个有理数，要求你将其 $\bmod 10^9+7$，如"备注"中所述。

备注

在打印有理数时，先写成分数的形式 $\frac{y}{x}$，其中 $x, y$ 为整数，且 $x$ 不在 $10^9 +7$ 的约束下除尽($x$ 在问题的约束下永远可以这样写成分数的形式)。

然后，你需要打印一个符合以下条件的整数 $z$，这个整数在 $0$ 到 $10^9 + 6$ 之间（包含 $0$ 和 $10^9 + 6$），满足 $xz \equiv y \pmod{10^9 + 7}$。

约束

• $2 \leq N \leq 2 \times 10^5$
• $1 \leq A_i,B_i \leq N$
• 给定的图是一棵树。

输入

从标准输入中以以下格式给出：

$N$

$A_1$ $B_1$

$:$

$A_{N-1}$ $B_{N-1}$

输出

打印 $S$ 的预期洞穴程度，$\bmod 10^9+7$。

3
1 2
2 3

125000001

如果顶点 $1, 2, 3$ 分别被涂成黑色、白色、黑色，则 $S$ 的洞穴程度为1。

否则，洞穴程度为0，因此预期洞穴程度为 $1/8$。

由于 $8 \times 125000001 \equiv 1 \pmod{10^9+7}$，我们应该打印 $125000001$。

4
1 2
2 3
3 4

375000003

洞穴程度期望为 $3/8$。

由于 $8 \times 375000003 \equiv 3 \pmod{10^9+7}$，我们应该打印 $375000003$。

4
1 2
1 3
1 4

250000002

洞穴程度期望为 $1/4$。

7
4 7
3 1
2 6
5 2
7 1
2 7

570312505