Surrounded Nodes

题目描述

给定一棵有 $N$ 个顶点的树 $T$。第 $i$ 条边连接顶点 $A_i$ 和 $B_i$（$1 \leq A_i,B_i \leq N$）。 现在，每个顶点以概率 $1/2$ 被涂成黑色，以概率 $1/2$ 被涂成白色，且各顶点之间独立选择。令 $S$ 为包含所有被涂成黑色的顶点的最小子树（连通子图）。（如果没有顶点被涂成黑色，则 $S$ 是空图。） 称 $S$ 的 holeyness 为 $S$ 中包含的白色顶点的数量。求 $S$ 的期望 holeyness。 由于答案是有理数，我们要求按照 Notes 中的描述对 $10^9+7$ 取模后输出。

输入格式

输入从标准输入按以下格式给出： $N$ $A_1$ $B_1$ : $A_{N-1}$ $B_{N-1}$

输出格式

输出 $S$ 的期望 holeyness，对 $10^9+7$ 取模。

3
1 2
2 3

125000001

4
1 2
2 3
3 4

375000003

4
1 2
1 3
1 4

250000002

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

570312505

提示

$2 \leq N \leq 2 \times 10^5$ $1 \leq A_i,B_i \leq N$ 给定的图是棵树。当你输出一个有理数时，先把它写成分数 $\frac{y}{x}$，其中 $x,y$ 为整数，且 $x$ 不被 $10^9 + 7$ 整除 （在本题约束下，这样的表示总是可能的）。 然后，你需要输出唯一一个在 $0$ 到 $10^9 + 6$（含）之间的整数 $z$，使得 $xz \equiv y \pmod{10^9 + 7}$。如果顶点 $1, 2, 3$ 分别被涂成黑、白、黑，则 $S$ 的 holeyness 为 $1$。 其他情况下，holeyness 为 $0$，因此期望 holeyness 为 $1/8$。 由于 $8 \times 125000001 \equiv 1 \pmod{10^9+7}$，我们应输出 $125000001$。
期望 holeyness 为 $3/8$。 由于 $8 \times 375000003 \equiv 3 \pmod{10^9+7}$，我们应输出 $375000003$。
期望 holeyness 为 $1/4$.

标签: AtCoder|abc149F

来源

AtCoder|abc149F