← 返回题目列表

AtCoder · abc149_f

F. 被包围的节点

中文机器翻译题面 查看原题

分数: 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