[ABC149F] Surrounded Nodes
题意翻译
### 题目描述
给定一棵 $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$
题目描述
[problemUrl]: https://atcoder.jp/contests/abc149/tasks/abc149_f
$ 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 $ で出力せよ。
输入输出样例
输入样例 #1
3
1 2
2 3
输出样例 #1
125000001
输入样例 #2
4
1 2
2 3
3 4
输出样例 #2
375000003
输入样例 #3
4
1 2
1 3
1 4
输出样例 #3
250000002
输入样例 #4
7
4 7
3 1
2 6
5 2
7 1
2 7
输出样例 #4
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 $ です。