分数: 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).