/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
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 で出力してください。
注記
有理数を出力する際は、まずその有理数を分数 \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
- 与えられるグラフは木である
入力
入力は以下の形式で標準入力から与えられる。
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 の穴あき度は 1 です。
それ以外の塗り方では S の穴あき度は 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
Score : 600 points
Problem Statement
Given is a tree T with N vertices. The i-th edge connects Vertex A_i and B_i (1 \leq A_i,B_i \leq N).
Now, each vertex is painted black with probability 1/2 and white with probability 1/2, which is chosen independently from other vertices. Then, let S be the smallest subtree (connected subgraph) of T containing all the vertices painted black. (If no vertex is painted black, S is the empty graph.)
Let the holeyness of S be the number of white vertices contained in S. Find the expected holeyness of S.
Since the answer is a rational number, we ask you to print it \bmod 10^9+7, as described in Notes.
Notes
When you print a rational number, first write it as a fraction \frac{y}{x}, where x, y are integers, and x is not divisible by 10^9 + 7 (under the constraints of the problem, such representation is always possible).
Then, you need to print the only integer z between 0 and 10^9 + 6, inclusive, that satisfies xz \equiv y \pmod{10^9 + 7}.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i,B_i \leq N
- The given graph is a tree.
Input
Input is given from Standard Input in the following format:
N
A_1 B_1
:
A_{N-1} B_{N-1}
Output
Print the expected holeyness of S, \bmod 10^9+7.
Sample Input 1
3 1 2 2 3
Sample Output 1
125000001
If the vertices 1, 2, 3 are painted black, white, black, respectively, the holeyness of S is 1.
Otherwise, the holeyness is 0, so the expected holeyness is 1/8.
Since 8 \times 125000001 \equiv 1 \pmod{10^9+7}, we should print 125000001.
Sample Input 2
4 1 2 2 3 3 4
Sample Output 2
375000003
The expected holeyness is 3/8.
Since 8 \times 375000003 \equiv 3 \pmod{10^9+7}, we should print 375000003.
Sample Input 3
4 1 2 1 3 1 4
Sample Output 3
250000002
The expected holeyness is 1/4.
Sample Input 4
7 4 7 3 1 2 6 5 2 7 1 2 7
Sample Output 4
570312505