题目描述

$1$ から $N$ の番号がついた $N$ 個の頂点と、$1$ から $N-1$ の番号がついた $N-1$ 本の辺からなる木が与えられます。 辺 $i$ は頂点 $a_i$ と頂点 $b_i$ を双方向につなぐ長さ $1$ の辺です。

すぬけ君はそれぞれの頂点を白か黒のどちらかで塗ります。 塗り方の 良さ は、白色の頂点同士の距離の最大値を $X$、黒色の頂点同士の距離の最大値を $Y$ として $\max(X,Y)$ です。 ここで、その色の頂点が存在しない場合の距離の最大値は $0$ とすることにします。

頂点への色の塗り方は $2^N$ 通りあります。それぞれの塗り方について良さを計算し、その総和を $10^{9}+7$ で割ったあまりを求めてください。

输入格式

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

$N$ $a_1$ $b_1$ $\vdots$ $a_{N-1}$ $b_{N-1}$

输出格式

それぞれの塗り方について良さを計算し、その総和を $10^{9}+7$ で割ったあまりを出力せよ。

题目大意

给定一棵 $n$ 个节点的树。你需要对每个节点黑白染色。

设 $x$ 表示白色点之间的最大距离，$y$ 表示黑色点之间的最大距离，那么定义一种染色的权值为 $\max(x,y)$。如果某种颜色没有出现那么对应的 $x/y$ 就是 $0$。

求所有 $2^n$ 种染色方式的权值和。对 $10^9+7$ 取模。

$\texttt{Data Range:} 2\le n\le 2\times 10^5$。

2
1 2

2

6
1 2
2 3
3 4
4 5
3 6

224

35
25 4
33 7
11 26
32 4
12 7
31 27
19 6
10 22
17 12
28 24
28 1
24 15
30 24
24 11
23 18
14 15
4 29
33 24
15 34
11 3
4 35
5 34
34 2
16 19
7 18
19 31
22 8
13 26
20 6
20 9
4 33
4 8
29 19
15 21

298219707

提示

制約

• 与えられる入力は全て整数
• $2\ \leq\ N\ \leq\ 2\ \times\ 10^{5}$
• $1\ \leq\ a_i,\ b_i\ \leq\ N$
• 与えられるグラフは木

Sample Explanation 1

- 頂点 $1,2$ の両方を同じ色で塗ったときの良さは $1$ で、異なる色で塗ったときの良さは $0$ です。 - 塗り方の良さの総和は $2$ となります。

Sample Explanation 3

- $10^{9}+7$ で割ったあまりを求めるのを忘れずに。