分数: 600 点
问题陈述
给定的是一棵树 T 与 N 顶点。的 i第一条边连接顶点 A_i 和 B_i (1 \leq A_i,B_i \leq N).
现在,每个顶点有概率被涂成黑色 1/2 和白色的概率 1/2,它是独立于其他顶点选择的。然后,让 S 是以下的最小子树(连通子图) T 包含所有涂成黑色的顶点。 (如果没有顶点被漆成黑色, S 是空图。)
让 多孔性 of S 是包含在 S。求出预期的孔隙度 S.
由于答案是有理数,因此我们要求您将其打印出来 \bmod 10^9+7,如注释中所述。
注释
打印有理数时,首先将其写为分数 \frac{y}{x},其中 x, y 是整数,并且 x 不能被整除 10^9 + 7 (在问题的约束下,这种表示总是可能的)。
然后,你需要打印唯一的整数 z 之间 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.
示例输入 1
3 1 2 2 3
示例输出 1
125000001
如果顶点 1, 2, 3 分别涂成黑色、白色、黑色,多孔性 S is 1.
否则,多孔度为 0,所以预期的多孔度是 1/8.
自从 8 \times 125000001 \equiv 1 \pmod{10^9+7},我们应该打印 125000001.
示例输入 2
4 1 2 2 3 3 4
示例输出 2
375000003
预期的多孔度是 3/8.
自从 8 \times 375000003 \equiv 3 \pmod{10^9+7},我们应该打印 375000003.
示例输入 3
4 1 2 1 3 1 4
示例输出 3
250000002
预期的多孔度是 1/4.
示例输入 4
7 4 7 3 1 2 6 5 2 7 1 2 7
示例输出 4
570312505