题目描述

$N$ 頂点の木 $T$ が与えられます。$i$ 番目の辺は頂点 $A_i$ と $B_i$ ($1\ \leq\ A_i,B_i\ \leq\ N$) を結びます。

$T$ の各頂点を、それぞれ独立に確率 $1/2$ で黒く、確率 $1/2$ で白く塗り、黒く塗られた頂点を全て含むような $T$ の最小の部分木 (連結な部分グラフ) を $S$ とします。(黒く塗られた頂点がないときは、$S$ は空グラフとします。)

$S$ の穴あき度を、$S$ に含まれる白く塗られた頂点の個数とします。$S$ の穴あき度の期待値を求めてください。

答えは有理数となるので、注記で述べるように $\bmod\ 10^9+7$ で出力してください。

输入格式

入力は以下の形式で標準入力から与えられる。

$N$ $A_1$ $B_1$ $:$ $A_{N-1}$ $B_{N-1}$

输出格式

$S$ の穴あき度の期待値を $\bmod\ 10^9+7$ で出力せよ。

题目大意

题目描述

给定一棵 $N$ 个节点的树 $T$ ，现在要给树上每个节点随机涂色，每个节点有 $\frac 1 2$ 的概率染成黑色， $\frac 1 2$ 的概率染成白色。对于一颗染过色的树，定义 $S$ 为包含树上所有被染成黑色的节点的，节点数最小的连通子图。定义 $S$ 的价值为 $S$ 中白色节点的个数。问 $S$ 的期望价值是多少。答案对 $10^9+7$ 取模。

输入格式

第一行一个整数 $N$ ，表示树的节点个数。
接下来 $N-1$ 行，每行两个整数 $A_i,B_i$ ，表示 $A_i,B_i$ 之间存在一条边。
保证给的图一定是一颗树。

输出格式

一个整数，表示 $S$ 的期望价值对 $10^9+7$ 取模的结果。

数据范围

• $2\le N \le2\times 10^5$
• $1\le A_i,B_i\le N$

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

提示

注記

有理数を出力する際は、まずその有理数を分数 $\frac{y}{x}$ として表してください。ここで、$x,y$ は整数であり、 $x$ は $10^9+7$ で割り切れてはなりません (この問題の制約下で、そのような表現は必ず可能です)。

そして、$xz\ \equiv\ y\ \pmod{10^9+7}$ を満たすような $0$ 以上 $10^9+6$ 以下の唯一の整数 $z$ を出力してください。

制約

• $2\ \leq\ N\ \leq\ 2\ \times\ 10^5$
• $1\ \leq\ A_i,B_i\ \leq\ N$
• 与えられるグラフは木である

Sample Explanation 1

頂点 $1,2,3$ の色がそれぞれ 黒,白,黒 となったとき、$S$ の穴あき度は $1$ です。 それ以外の塗り方では $S$ の穴あき度は $0$ であるため、穴あき度の期待値は $1/8$ です。 $8\ \times\ 125000001\ \equiv\ 1\ \pmod{10^9+7}$ より、$125000001$ を出力します。

Sample Explanation 2

期待値は $3/8$ です。 $8\ \times\ 375000003\ \equiv\ 3\ \pmod{10^9+7}$ より、$375000003$ を出力します。

Sample Explanation 3

期待値は $1/4$ です。