You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

[ARC108F] Paint Tree

题目描述

给定一棵 $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$。

输入格式

第一行一个整数 $n$ ，接下来 $n-1$ 行每行两个整数 $a_i,b_i$ 表示一条树边。

输出格式

一个整数表示答案对 $10^{9}+7$ 取模的结果。

样例 #1

样例输入 #1

2
1 2

样例输出 #1

2

样例 #2

样例输入 #2

6
1 2
2 3
3 4
4 5
3 6

样例输出 #2

224

样例 #3

样例输入 #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

数据范围

• $2\ \leq\ N\ \leq\ 2\ \times\ 10^{5}$
• $1\ \leq\ a_i,\ b_i\ \leq\ N$

样例解释 1

- 顶点 $1,2$ 同色时权值为 $1$ ，异色时权值为 $0$ ，故总和为 $2$ 。