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-----
2
1 2

-----Sample Output-----
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.

Difficulty: VERY_HARD

Starter code:

Solutions:
from collections import deque
n = int(input())
graph = [[] for i in range(n + 1)]
for _ in range(n - 1):
	(i, j) = map(int, input().split())
	graph[i].append(j)
	graph[j].append(i)
mod = 10 ** 9 + 7

def bfs(x):
	q = deque([(0, x, 0)])
	dist = {x: 0}
	while q:
		(step, i, par) = q.popleft()
		dist[i] = step
		for j in graph[i]:
			if j == par:
				continue
			q.append((step + 1, j, i))
	return [step, i, dist]
(_, black, _) = bfs(1)
(maxdist, white, b_dist) = bfs(black)
(_, _, w_dist) = bfs(white)
mindls = float('-inf')
maxdls = [0] * n
for i in range(1, n + 1):
	if i in (white, black):
		continue
	mindls = max(mindls, min(w_dist[i], b_dist[i]))
	maxdls[max(w_dist[i], b_dist[i])] += 1
ans = pow(2, n - 1, mod) * maxdist % mod
pre = 0
for i in range(1, maxdist + 1):
	if i == maxdist and (not maxdls[i]):
		continue
	maxdls[i] += maxdls[i - 1]
	if mindls > i:
		continue
	ans += (pow(2, maxdls[i], mod) - pre) * i * 2
	ans %= mod
	pre = pow(2, maxdls[i], mod)
print(ans)


MOD = 10 ** 9 + 7
from collections import deque
(N,) = list(map(int, input().split()))
G = [set() for _ in range(N + 1)]
for _ in range(N - 1):
	(a, b) = list(map(int, input().split()))
	G[a].add(b)
	G[b].add(a)
queue = deque([1])
vs = set([1])
dist = [0] * (N + 1)
mx = 0
mxv = 1
while queue:
	v = queue.popleft()
	for u in G[v]:
		if u in vs:
			continue
		vs.add(u)
		queue.append(u)
		dist[u] = dist[v] + 1
		if mx < dist[u]:
			mx = dist[u]
			mxv = u
queue = deque([mxv])
vs = set([mxv])
dist2 = [0] * (N + 1)
mx2 = 0
mxv2 = 1
while queue:
	v = queue.popleft()
	for u in G[v]:
		if u in vs:
			continue
		vs.add(u)
		queue.append(u)
		dist2[u] = dist2[v] + 1
		if mx2 < dist2[u]:
			mx2 = dist2[u]
			mxv2 = u
queue = deque([mxv2])
vs = set([mxv2])
dist3 = [0] * (N + 1)
while queue:
	v = queue.popleft()
	for u in G[v]:
		if u in vs:
			continue
		vs.add(u)
		queue.append(u)
		dist3[u] = dist3[v] + 1
r = 0
for i in range(1, N + 1):
	x = min(dist2[i], dist3[i])
	r = max(x, r)
X = [0] * (N + 1)
for i in range(1, N + 1):
	y = max(dist2[i], dist3[i])
	X[y] += 1
for i in range(N - 1, r - 1, -1):
	X[i] = X[i] + X[i + 1]
X.append(0)
d = [0] * (N + 1)
for i in range(N, r - 1, -1):
	x = min(N - X[i + 1] + 1, N)
	d[i] = pow(2, x, MOD)
R = 0
for i in range(r, N + 1):
	R = (R + i * (d[i] - d[i - 1])) % MOD
print(R)


import sys
input = lambda : sys.stdin.readline().rstrip()
from collections import deque
N = int(input())
X = [[] for _ in range(N)]
for _ in range(N - 1):
	(a, b) = map(int, input().split())
	X[a - 1].append(b - 1)
	X[b - 1].append(a - 1)

def farthest(i):
	L = [-1] * N
	L[i] = 0
	d = 0
	post = [i]
	while len(post) > 0:
		d += 1
		pre = post
		post = []
		for j in pre:
			for k in X[j]:
				if L[k] < 0:
					L[k] = d
					post.append(k)
	return (pre[0], d - 1)
(s, _) = farthest(0)
(t, d) = farthest(s)

def BFS_dist(n, E, i0=0):
	Q = deque([i0])
	D = [-1] * n
	D[i0] = 0
	while Q:
		x = Q.popleft()
		for c in E[x]:
			if D[c] == -1:
				D[c] = D[x] + 1
				Q.append(c)
	return D
D1 = BFS_dist(N, X, s)
D2 = BFS_dist(N, X, t)
Y = [0] * (d + 1)
ma = 0
for i in range(N):
	if i == s or i == t:
		continue
	(a, b) = sorted((D1[i], D2[i]))
	ma = max(ma, a)
	Y[b] += 1
Y[d] += 1
P = 10 ** 9 + 7
i2 = P + 1 >> 1
s = 1
ans = d
for i in range(d, ma, -1):
	if Y[i]:
		s = pow(i2, Y[i], P) * s % P
	ans -= s
	if ans < 0:
		ans += P
print(ans * pow(2, N, P) % P)


n = int(input())
ab = [list(map(int, input().split())) for i in range(n - 1)]
graph = [[] for i in range(n + 1)]
for (a, b) in ab:
	graph[a].append(b)
	graph[b].append(a)
mod = 10 ** 9 + 7
start = 1
stack = [1]
s_dist = [0] + [0] + [10 ** 9] * (n - 1)
while stack:
	x = stack.pop()
	for y in graph[x]:
		if s_dist[y] > s_dist[x]:
			s_dist[y] = s_dist[x] + 1
			stack.append(y)
maxdist = max(s_dist)
black = s_dist.index(maxdist)
b_dist = [10 ** 9] * (n + 1)
b_dist[0] = 0
b_dist[black] = 0
stack = [black]
while stack:
	x = stack.pop()
	for y in graph[x]:
		if b_dist[y] > b_dist[x]:
			b_dist[y] = b_dist[x] + 1
			stack.append(y)
maxdist = max(b_dist)
white = b_dist.index(maxdist)
w_dist = [10 ** 9] * (n + 1)
w_dist[0] = 0
w_dist[white] = 0
stack = [white]
while stack:
	x = stack.pop()
	for y in graph[x]:
		if w_dist[y] > w_dist[x]:
			w_dist[y] = w_dist[x] + 1
			stack.append(y)
mindls = [0] * n
maxdls = [0] * n
for i in range(1, n + 1):
	if i in (white, black):
		continue
	mindls[min(w_dist[i], b_dist[i])] += 1
	maxdls[max(w_dist[i], b_dist[i])] += 1
ans = pow(2, n - 1, mod) * maxdist % mod
number = 0
for i in range(1, maxdist + 1):
	if i == maxdist and maxdls[i] == 0:
		continue
	maxdls[i] += maxdls[i - 1]
	if i < maxdist and mindls[i + 1]:
		continue
	ans += (pow(2, maxdls[i], mod) - number) * i * 2
	ans %= mod
	number = pow(2, maxdls[i], mod)
print(ans)


from collections import deque, defaultdict

def diameter(n, links):
	q = deque([0])
	stacked = {0}
	v = -1
	while q:
		v = q.popleft()
		for u in links[v]:
			if u not in stacked:
				q.append(u)
				stacked.add(u)
	v1 = v
	q = deque([(0, v1)])
	distances1 = [-1] * n
	distances1[v1] = 0
	while q:
		(d, v) = q.popleft()
		for u in links[v]:
			if distances1[u] == -1:
				q.append((d + 1, u))
				distances1[u] = d + 1
	v2 = v
	q = deque([(0, v2)])
	distances2 = [-1] * n
	distances2[v2] = 0
	while q:
		(d, v) = q.popleft()
		for u in links[v]:
			if distances2[u] == -1:
				q.append((d + 1, u))
				distances2[u] = d + 1
	return (v1, v2, distances1, distances2)

def solve(n, links):
	MOD = 10 ** 9 + 7
	(v1, v2, distances1, distances2) = diameter(n, links)
	ans = distances1[v2] * pow(2, n - 2, MOD) % MOD
	farther = defaultdict(lambda : [0, 0])
	for i in range(n):
		if i == v1 or i == v2:
			continue
		d1 = distances1[i]
		d2 = distances2[i]
		mx = max(d1, d2)
		mn = min(d1, d2)
		farther[mx][0] += 1
		farther[mx][1] = max(farther[mx][1], mn)
	m = n - 2
	max_smaller_d = 0
	for d in sorted(list(farther.keys()), reverse=True):
		if d <= max_smaller_d:
			ans = (ans + max_smaller_d * pow(2, m, MOD)) % MOD
			break
		(cnt, mn) = farther[d]
		m -= cnt
		ans = (ans + d * (pow(2, cnt, MOD) - 1) * pow(2, m, MOD)) % MOD
		max_smaller_d = max(max_smaller_d, mn)
	else:
		ans = (ans + max_smaller_d * pow(2, m, MOD)) % MOD
	return ans * 2 % MOD
n = int(input())
links = [set() for _ in range(n)]
for _ in range(n - 1):
	(a, b) = list(map(int, input().split()))
	a -= 1
	b -= 1
	links[a].add(b)
	links[b].add(a)
print(solve(n, links))


from collections import deque
n = int(input())
graph = [[] for i in range(n + 1)]
for _ in range(n - 1):
	(i, j) = map(int, input().split())
	graph[i].append(j)
	graph[j].append(i)
mod = 10 ** 9 + 7

def bfs(x):
	q = deque([(0, x, 0)])
	while q:
		(step, i, par) = q.popleft()
		for j in graph[i]:
			if j == par:
				continue
			q.append((step + 1, j, i))
	return [step, i]
(maxdist, black) = bfs(1)
b_dist = [10 ** 9] * (n + 1)
b_dist[0] = 0
b_dist[black] = 0
stack = [black]
while stack:
	x = stack.pop()
	for y in graph[x]:
		if b_dist[y] > b_dist[x] + 1:
			b_dist[y] = b_dist[x] + 1
			stack.append(y)
maxdist = max(b_dist)
white = b_dist.index(maxdist)
w_dist = [10 ** 9] * (n + 1)
w_dist[0] = 0
w_dist[white] = 0
stack = [white]
while stack:
	x = stack.pop()
	for y in graph[x]:
		if w_dist[y] > w_dist[x] + 1:
			w_dist[y] = w_dist[x] + 1
			stack.append(y)
mindls = [0] * n
maxdls = [0] * n
for i in range(1, n + 1):
	if i in (white, black):
		continue
	mindls[min(w_dist[i], b_dist[i])] += 1
	maxdls[max(w_dist[i], b_dist[i])] += 1
ans = pow(2, n - 1, mod) * maxdist % mod
number = 0
for i in range(1, maxdist + 1):
	if i == maxdist and maxdls[i] == 0:
		continue
	maxdls[i] += maxdls[i - 1]
	if i < maxdist and mindls[i + 1]:
		continue
	ans += (pow(2, maxdls[i], mod) - number) * i * 2
	ans %= mod
	number = pow(2, maxdls[i], mod)
print(ans)


import sys
input = sys.stdin.readline
from collections import Counter
N = int(input())
E = [[] for i in range(N)]
for i in range(N - 1):
	(x, y) = map(int, input().split())
	x -= 1
	y -= 1
	E[x].append(y)
	E[y].append(x)
mod = 10 ** 9 + 7

def dfs(x):
	DIS = [-1] * N
	DIS[x] = 0
	Q = [x]
	while Q:
		x = Q.pop()
		for to in E[x]:
			if DIS[to] == -1:
				DIS[to] = DIS[x] + 1
				Q.append(to)
	return DIS
D0 = dfs(0)
L = D0.index(max(D0))
DL = dfs(L)
R = DL.index(max(DL))
DR = dfs(R)
MIN = [min(DL[i], DR[i]) for i in range(N)]
MAX = [max(DL[i], DR[i]) for i in range(N)]
C = Counter(MIN)
half = pow(2, mod - 2, mod) % mod
ALL = pow(2, N, mod)
ANS = max(DR) * ALL * half % mod
MAX.sort()
dind = 0
ANS = (ANS + max(MIN) * ALL * half) % mod
for d in range(max(MIN) + 1, max(DR) + 1):
	while dind < N and MAX[dind] < d:
		dind += 1
	ANS = (ANS + 2 * (ALL * half * half - pow(2, dind, mod))) % mod
print(ANS)


import sys
from sys import stdin
from collections import deque

def NC_Dij(lis, start):
	ret = [float('inf')] * len(lis)
	ret[start] = 0
	q = deque([start])
	plis = [i for i in range(len(lis))]
	while len(q) > 0:
		now = q.popleft()
		for nex in lis[now]:
			if ret[nex] > ret[now] + 1:
				ret[nex] = ret[now] + 1
				plis[nex] = now
				q.append(nex)
	return (ret, plis)
mod = 10 ** 9 + 7
N = int(stdin.readline())
lis = [[] for i in range(N)]
for i in range(N - 1):
	(a, b) = list(map(int, stdin.readline().split()))
	a -= 1
	b -= 1
	lis[a].append(b)
	lis[b].append(a)
(D0, tmp) = NC_Dij(lis, 0)
p1 = 0
for i in range(N):
	if D0[i] > D0[p1]:
		p1 = i
(D1, tmp) = NC_Dij(lis, p1)
p2 = p1
for i in range(N):
	if D1[i] > D1[p2]:
		p2 = i
(D2, tmp) = NC_Dij(lis, p2)
DL1 = []
for i in range(N):
	DL1.append((D1[i], i))
DL2 = []
for i in range(N):
	DL2.append((D2[i], i))
DL1.sort()
DL1.reverse()
DL2.sort()
DL2.reverse()
anslis = [0] * N
visit = [0] * N
two = 0
zero = N
for X in range(N):
	while len(DL1) > 0 and DL1[-1][0] == X:
		(tmp, v) = DL1[-1]
		del DL1[-1]
		if visit[v] == 0:
			zero -= 1
		elif visit[v] == 1:
			two += 1
		visit[v] += 1
	while len(DL2) > 0 and DL2[-1][0] == X:
		(tmp, v) = DL2[-1]
		del DL2[-1]
		if visit[v] == 0:
			zero -= 1
		elif visit[v] == 1:
			two += 1
		visit[v] += 1
	if two == N:
		anslis[X] = pow(2, N, mod)
	elif zero == 0:
		anslis[X] = 2 * pow(2, two, mod)
ans = 0
for i in range(1, N):
	ans += (anslis[i] - anslis[i - 1]) * i
print(ans % mod)