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: competition

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
#print(mxv, mxv2)
#print(dist2)
#print(dist3)
r = 0
for i in range(1, N+1):
    x = min(dist2[i], dist3[i])
    r = max(x, r)
# 絶対に良さはr以上になる
#　なぜならx = rとなるノードをどちらの色に塗っても、良さはrに決まるから...

X = [0]*(N+1)
for i in range(1, N+1):
    y = max(dist2[i], dist3[i])
    X[y] += 1

#print(r)
for i in range(N-1, r-1, -1):
    X[i] = X[i] + X[i+1]

#print(X)
# d[i] = dがi以下になる場合の数
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) 
#print(d)

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)

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
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] + 1:
      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] + 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)

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)

    # print(v1, v2)
    # print(distances1)
    # print(distances2)
    # print(farther)

    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)

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 = [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
pre = 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) - pre) * i * 2
  ans %= mod
  pre = pow(2, maxdls[i], mod)
print(ans)

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
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
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 maxdls[i] == 0:
    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)

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)]

half=pow(2,mod-2,mod)%mod
ALL=pow(2,N-1,mod)
ANS=max(DR)*ALL%mod

MAX.sort()

dind=0
ANS=(ANS+max(MIN)*ALL)%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-pow(2,dind,mod)))%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)


"""

答えがX未満になる場合の数がわかればおk
→距離がX以上となるすべての点対間において違う色で塗られている

直径を考えてみる
端点を白とするとからX以上の距離は全て黒
もう片方の端点からX以上の距離は全て白にぬる
当然かぶったらout

かぶらなかったらok?
仮定する

実装は
各Xに関して、両方からX以内の頂点の数を数え上げる

"""

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))