← 返回题目列表

AtCoder · arc108_f

F. 油漆树

中文机器翻译题面 查看原题

分数: 900 点

问题陈述

给定的是一棵树 N 顶点编号 1 to N,和 N-1 边编号 1 to N-1。 边缘 i 连接顶点 a_i 和 b_i 双向且长度为 1.

Snuke 会将每个顶点涂成白色或黑色。 的 善良 第 $$$i$$$ 个孩子的 绘制图形的方法是 \max(X, Y),其中 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).