F - Paint Tree Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 900 点

問題文

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 で割ったあまりを求めてください。

制約

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

入力

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

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

出力

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

入力例 1

2
1 2

出力例 1

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

入力例 2

6
1 2
2 3
3 4
4 5
3 6

出力例 2

224

入力例 3

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

出力例 3

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

Score : 900 points

Problem Statement

Given is a tree with N vertices numbered 1 to N, and N-1 edges numbered 1 to N-1. Edge i connects Vertex a_i and b_i bidirectionally and has a length of 1.

Snuke will paint each vertex white or black. The niceness of a way of painting the graph is \max(X, Y), where X is the maximum among the distances between white vertices, and Y is the maximum among the distances between black vertices. Here, if there is no vertex of one color, we consider the maximum among the distances between vertices of that color to be 0.

There are 2^N ways of painting the graph. Compute the sum of the nicenesses of all those ways, modulo (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
\vdots
a_{N-1} b_{N-1}

Output

Print the sum of the nicenesses of the ways of painting the graph, modulo (10^{9}+7).

Sample Input 1

2
1 2

Sample Output 1

2
  • If we paint Vertex 1 and 2 the same color, the niceness will be 1; if we paint them different colors, the niceness will be 0.
  • The sum of those nicenesses is 2.

Sample Input 2

6
1 2
2 3
3 4
4 5
3 6

Sample Output 2

224

Sample Input 3

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

Sample Output 3

298219707
  • Be sure to compute the sum modulo (10^{9}+7).