Problem:
 Score : 600 points    Problem Statement Given is a tree T with N vertices. The i -th edge connects Vertex A_i and B_i ( 1 \leq A_i,B_i \leq N ).  Now, each vertex is painted black with probability 1/2 and white with probability 1/2 , which is chosen independently from other vertices. Then, let S be the smallest subtree (connected subgraph) of T containing all the vertices painted black. (If no vertex is painted black, S is the empty graph.)  Let the holeyness of S be the number of white vertices contained in S . Find the expected holeyness of S .  Since the answer is a rational number, we ask you to print it \bmod 10^9+7 , as described in Notes.      Notes When you print a rational number, first write it as a fraction \frac{y}{x} , where x, y are integers, and x is not divisible by 10^9 + 7 (under the constraints of the problem, such representation is always possible).  Then, you need to print the only integer z between 0 and 10^9 + 6 , inclusive, that satisfies xz \equiv y \pmod{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  :  A_{N-1}  B_{N-1}       Output Print the expected holeyness of S , \bmod 10^9+7 .        Sample Input 1 3
1 2
2 3      Sample Output 1 125000001  If the vertices 1, 2, 3 are painted black, white, black, respectively, the holeyness of S is 1 .  Otherwise, the holeyness is 0 , so the expected holeyness is 1/8 .  Since 8 \times 125000001 \equiv 1 \pmod{10^9+7} , we should print 125000001 .       Sample Input 2 4
1 2
2 3
3 4      Sample Output 2 375000003  The expected holeyness is 3/8 .  Since 8 \times 375000003 \equiv 3 \pmod{10^9+7} , we should print 375000003 .       Sample Input 3 4
1 2
1 3
1 4      Sample Output 3 250000002  The expected holeyness is 1/4 .       Sample Input 4 7
4 7
3 1
2 6
5 2
7 1
2 7      Sample Output 4 570312505

Solution (Python):

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
MOD = 10**9 + 7

n = int(input())
edge = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = [int(item) - 1 for item in input().split()]
    edge[a].append(b)
    edge[b].append(a)

childs = [[] for _ in range(n)]
def dfs(p, v):
    val = 1
    for nv in edge[v]:
        if nv == p:
            continue
        ret = dfs(v, nv)
        val += ret
        childs[v].append(ret)
    if val != n:
        childs[v].append(n - val)
    return val

dfs(-1, 0)
total_pattern = pow(2, n, MOD)
total_pattern_inv = pow(total_pattern, MOD-2, MOD)
inv2 = pow(2, MOD-2, MOD)
pow2_table = [1]
for i in range(2 * 10**5):
    pow2_table.append(pow2_table[-1] * 2 % MOD)
ans = 0
for line in childs:
    pattern_ok = 0
    if len(line) == 1:
        continue
    for item in line:
        pattern_ok += pow2_table[item] - 1
    pattern_ok += 1
    ans += (total_pattern * inv2 - pattern_ok) * total_pattern_inv
    ans %= MOD
print(ans)

Solution (Python):
from sys import stdin
f_i = stdin

N = int(f_i.readline())

adj = [[] for i in range(N)]
for i in range(N - 1):
    A, B = map(int, f_i.readline().split())
    A -= 1
    B -= 1
    adj[A].append(B)
    adj[B].append(A)

mod = 10 ** 9 + 7

pow2 = [1] * (N + 1)
for i, j in zip(range(N), range(1, N + 1)):
    pow2[j] = pow2[i] * 2 % mod

from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

ans = 0

def dfs(node, parent):
    global ans
    cnt = 1
    
    for child in adj[node]:
        if child != parent:
            cnt += dfs(child, node)
    
    ans += (pow2[cnt] - 1) * (pow2[N-cnt] - 1)
    ans %= mod
    
    return cnt

dfs(0, None)

ans = (ans - N * pow2[N-1] + pow2[N] - 1) % mod
ans = ans * pow(pow2[N], mod - 2, mod) % mod

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

mod = 10 ** 9 + 7

N = int(input())
vec = [[] for _ in range(N)]
for _ in range(N-1) :
  A, B = map(int, input().split())
  vec[A-1].append(B-1)
  vec[B-1].append(A-1)

sub_size = [[] for _ in range(N)]

def dfs(cur=0, pre=-1) :
  s = 0
  for nex in vec[cur] :
    if nex == pre :
      continue
    t = dfs(nex, cur)
    s += t
    sub_size[cur].append(t)
  if s != N - 1 :
    sub_size[cur].append(N - 1 - s)

  return s + 1

dfs()

power = [1]
for _ in range(N) :
  power.append(power[-1]*2%mod)

ret = 0
for i in range(N) :
  tmp = power[N-1]-1
  for ss in sub_size[i] :
    tmp -= power[ss]-1
  ret += tmp

ret = ret*pow(power[N], mod - 2, mod)% mod

print(ret)

Solution (Python):
from sys import setrecursionlimit
setrecursionlimit(2 * (10 ** 5))

n = int(input())
ab = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(n-1)]

e = [[] for _ in range(n)]

for a, b in ab:
    e[a].append(b)
    e[b].append(a)

MOD = 10 ** 9 + 7

d = []

def modinv(x):
    a = x
    b = MOD
    u = 1
    v = 0
    while b:
        t = a // b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    u %= MOD
    if u < 0:
        u += MOD
    return u

def dfs(x, p):
    if len(e[x]) == 1:
        if e[x][0] == p:
            d.append(1)
            return 1
    ret = 1
    for z in e[x]:
        if z == p:
            continue
        ret += dfs(z, x)
    if x != 0:
        
        d.append(ret)
    return ret

dfs(0,-1)

f = []
w = 1
for i in range(n + 1):
    f.append(w)
    w = (w * 2) % MOD



ans = 0
for x in d:
    ans += ((f[x] - 1) * (f[n-x] - 1)) % MOD
    ans %= MOD



ans = (ans - f[n-1] * n + f[n] - 1 + MOD) % MOD



ans = (ans * modinv(f[n])) % MOD

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(200200)
input = sys.stdin.readline
MOD=10**9+7
N = int(input())
AB = [tuple(map(int, input().split())) for _ in range(N-1)]
G = [[] for _ in range(N)]
for i, (a, b) in enumerate(AB):
    a -= 1
    b -= 1
    G[a].append((b, i))
    G[b].append((a, i))

P = [0] * N
visited = [False] * N
visited[0] = True
def dfs(x, i):
    e = 1
    for v, c in G[x]:
        if not visited[v]:
            visited[v] = True
            e += dfs(v, c)
    P[i] = e
    return e

dfs(0, -1)
W = [1] * (N + 1)
inv_2 = pow(2, MOD-2, MOD)
for i in range(N):
    W[i+1] = W[i]*inv_2%MOD
ans = (W[N] + 1) * (N - 1) % MOD
for i in range(N-1):
    ans -= W[P[i]] + W[N-P[i]]
    ans %= MOD
print((ans - inv_2*N - W[N] + 1) % MOD)

Solution (Python):

from collections import defaultdict,deque
import sys
import math
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
mod = 1000000007

def solve():
    n = I()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    q = deque([0])
    d = [0]*n
    d[0] = 1
    pre = [None]*n
    while q:
        x = q.popleft()
        nd = d[x]+1
        for y in v[x]:
            if not d[y]:
                d[y] = nd
                pre[y] = x
                q.append(y)
    V = list(range(1,n))
    V.sort(key = lambda x:-d[x])
    size = [1]*n
    for i in V:
        size[pre[i]] += size[i]
    inv = pow(2,mod-2,mod)
    ans = (1-pow(inv,n,mod)-n*inv)%mod
    p = [pow(inv,i,mod) for i in range(n)]
    for i in range(1,n):
        a = size[i]
        b = n-a
        ans += (p[a]-1)*(p[b]-1)%mod
        ans %= mod
    print(ans)
    return


if __name__ == "__main__":
    solve()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    q = deque([0])
    d = [0]*n
    d[0] = 1
    pre = [None]*n
    while q:
        x = q.popleft()
        nd = d[x]+1
        for y in v[x]:
            if not d[y]:
                d[y] = nd
                pre[y] = x
                q.append(y)
    V = list(range(1,n))
    V.sort(key = lambda x:-d[x])
    size = [1]*n
    for i in V:
        size[pre[i]] += size[i]
    inv = pow(2,mod-2,mod)
    ans = (1-pow(inv,n,mod)-n*inv)%mod
    p = [pow(inv,i,mod) for i in range(n)]
    for i in range(1,n):
        a = size[i]
        b = n-a
        ans += (p[a]-1)*(p[b]-1)%mod
        ans %= mod
    print(ans)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
import sys,heapq
input = sys.stdin.readline


def main():
    mod = 10**9+7
    n = int(input())
    edge = [[] for _ in [0]*n]
    for i in range(n-1):
        a,b = map(int,input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
    
    
    p = -1
    ma = -1
    for i in range(n):
        if len(edge[i]) > ma:
            p = i
            ma = len(edge[i])

    
    par = [-2]*n
    par[p] = -1
    order = []
    tank = [p]
    while tank:
        x = tank.pop()
        order.append(x)
        for elt in edge[x]:
            if par[elt] == -2:
                par[elt] = x
                tank.append(elt)
        

    
    size = [1]*n    
    for i in range(n-1,0,-1):
        now = order[i]
        size[par[now]] += size[now]
    
    se_N1 = pow(2,n-1,mod)

    res = 0
    for i in range(n):
        if size[i] == 1:
            continue
        
        Q = []
        for elt in edge[i]:
            if elt == par[i]:
                Q.append(n-size[i])
            else:
                Q.append(size[elt])
        res = (res + se_N1)%mod
        cpm = 1
        for e in Q:
            cpm = (cpm + pow(2,e,mod) - 1)%mod
        res = (res-cpm)%mod

    print(res*pow(2,n*(mod-2),mod)%mod) 

    





if __name__ == '__main__':
    main()

Solution (Python):
class Tree:
  C, RL = {}, {}
  R, N, D, S, P = None, None, None, None, None
  SN = None
  def __init__(s, num):
    s.N = num
  def set(s, a, b):
    if a in s.C: s.C[a].append(b)
    else: s.C[a] = [b]
    if b in s.C: s.C[b].append(a)
    else: s.C[b] = [a]
  def makeRank(s, root):
    s.R = [0] * s.N 
    s.R[root] = 1
    s.RL[1] = [root] 
    s.S = [[] for _ in range(s.N)] 
    s.P = [-1] * s.N 
    F = [root]
    s.D = 2
    while F != []:
      Ft = []
      s.RL[s.D] = []
      for i in F:
        for j in s.C[i]:
          if s.R[j] == 0:
            s.R[j] = s.D
            Ft.append(j)
            s.RL[s.D].append(j)
            s.S[i].append(j)
            s.P[j] = i
      s.D += 1
      F = Ft
  def dfs(s, x): 
    t = [-1] * s.N
    S = [x]
    ans = x
    ansn = 0
    t[x] = 0
    while S != []:
      k = S.pop()
      for i in s.C[k]:
        if t[i] == -1:
          t[i] = t[k] + 1
          S.append(i)
          if t[i] > ansn:
            ansn = t[i]
            ans = i
    return ans, ansn
  def getDi(s, x = 0): 
    a, _ = s.dfs(x)
    b, ans = s.dfs(a)
    return ans
  def getDeep(s, x): 
    ans = 0
    if x in s.S:
      for i in s.S[x]:
        ans = max(ans, s.getDeep(i))
      return ans + 1
    else:
      return 0
  def getParent(s, x, n): 
    if n == 0:
      return x
    if s.P[x] == -1:
      return -n
    return s.getParent(s.P[x], n - 1)
  def countSon(s):
    s.SN = [0] * s.N
    for i in range(s.D - 1, 0, -1):
      for j in s.RL[i]:
        cnt = 1
        for k in s.S[j]:
          cnt += s.SN[k]
        s.SN[j] = cnt

class powmod():
  F = [1, 2]
  Fi = [1, 2]
  I = [0, 1]
  def __init__(self, num, mod):
    self.MOD = mod
    k = 2
    for i in range(2, num + 1):
      self.F.append((self.F[-1] * k) % mod)
      self.I.append(mod - self.I[mod % k] * (mod // k) % mod)
      self.Fi.append(self.Fi[-1] * self.I[k] % mod)

class Inv:
  def __init__(s, mod):
    s.MOD = mod
  def modpow(s, a, n):
    res = 1
    while n > 0:
      if n & 1:
        res = res * a % s.MOD
      a = a * a % s.MOD
      n >>= 1
    return res
  def invx(s, a):
    return s.modpow(a, s.MOD - 2)
  def invL(s, a, n):
    ia = s.invx(a)
    L = [1] * (n + 1)
    for i in range(1, n + 1):
      L[i] = L[i - 1] * ia % s.MOD
    return L


N = int(input())
AB = [list(map(int, input().split())) for _ in range(N - 1)]

T = Tree(N)
L = [0] * N
for a, b in AB:
  T.set(a - 1, b - 1)
  L[a - 1] += 1
  L[b - 1] += 1

for i in range(N):
  if L[i] == 1:
    root = i

T.makeRank(root)
T.countSon()

MOD = 10 ** 9 + 7
ans = 0


PM = powmod(N, MOD)
I = Inv(MOD)
y = I.invx(PM.F[N])

ans = 0
for i in range(N):
  if i == root: continue
  if T.S[i] == []: continue
  L = []
  cnt = 0
  for j in T.S[i]:
    L.append(T.SN[j])
    cnt += T.SN[j]
  L.append(N - cnt - 1)

  t = PM.F[N - 1] - 1
  for j in L:
    t = t - PM.F[j] + 1
    if t < 0:
      t += MOD
  ans = (ans + t * y) % MOD

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

N=int(input())

E=[[] for i in range(N+1)]

for i in range(N-1):
    x,y=map(int,input().split())
    E[x].append(y)
    E[y].append(x)

mod=10**9+7

from collections import deque
Q=deque()

USE=[0]*(N+1)
Q.append(1)
H=[0]*(N+1)
H[1]=1
USE[1]=1

while Q:
    x=Q.pop()
    for to in E[x]:
        if USE[to]==0:
            USE[to]=1
            H[to]=H[x]+1
            Q.append(to)

EH=[(h,ind+1) for ind,h in enumerate(H[1:])]
EH.sort(reverse=True)

COME=[1]*(N+1)
USE=[0]*(N+1)

for h,ind in EH:
    USE[ind]=1
    for to in E[ind]:
        if USE[to]==0:
            COME[to]+=COME[ind]

ANS=0

POW2=[1]
for i in range(N+1):
    POW2.append(POW2[-1]*2%mod)

for i in range(1,N+1):
    SCORE=[]
    for j in E[i]:
        if COME[j]<COME[i]:
            SCORE.append(COME[j])

    if sum(SCORE)<N-1:
        SCORE.append(N-sum(SCORE)-1)

    AV=1

    for s in SCORE:
        AV+=POW2[s]-1

    ANS+=POW2[N-1]-AV
    

print((ANS*pow(POW2[N],mod-2,mod))%mod)

Solution (Python):
N=int(input())

E=[[] for i in range(N+1)]

for i in range(N-1):
    x,y=map(int,input().split())
    E[x].append(y)
    E[y].append(x)

mod=10**9+7

from collections import deque
Q=deque()

USE=[0]*(N+1)
Q.append(1)
H=[0]*(N+1)
H[1]=1
USE[1]=1

while Q:
    x=Q.pop()
    for to in E[x]:
        if USE[to]==0:
            USE[to]=1
            H[to]=H[x]+1
            Q.append(to)

EH=[(h,ind+1) for ind,h in enumerate(H[1:])]
EH.sort(reverse=True)

COME=[1]*(N+1)
USE=[0]*(N+1)

for h,ind in EH:
    USE[ind]=1
    for to in E[ind]:
        if USE[to]==0:
            COME[to]+=COME[ind]

ANS=0

POW2=[1]
for i in range(N+1):
    POW2.append(POW2[-1]*2%mod)

for i in range(1,N+1):
    SCORE=[]
    for j in E[i]:
        if COME[j]<COME[i]:
            SCORE.append(COME[j])

    if sum(SCORE)<N-1:
        SCORE.append(N-sum(SCORE)-1)

    AV=1

    for s in SCORE:
        AV+=POW2[s]-1

    ANS+=POW2[N-1]-AV
    

print((ANS*pow(POW2[N],mod-2,mod))%mod)

Solution (Python):
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

N=II()
AB = [LI() for _ in range(N-1)]

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

root = 1
parent = [0] * (N+1)
order = []
stack = [root]
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]: continue
        parent[y] = x
        stack.append(y)

x = (DVSR + 1) // 2
PWR=[1]*(N+1)
RWP=[1]*(N+1)

for i in range(1,N+1):
    PWR[i] = PWR[i-1] * 2 % DVSR
    RWP[i] = RWP[i-1] * x % DVSR

answer = 0
size = [1] * (N+1)
for v in order[::-1]:
    p = parent[v]
    size[p] += size[v]
    A = [size[w] for w in graph[v] if w != p]
    if v != root: A.append(N - 1 - sum(A))
    if len(A) == 1: continue
    prod = 1
    coef = 1
    for x in A:
        prod *= RWP[x]
        prod %= DVSR
        coef += (PWR[x] - 1)
    E = 1 - prod * coef % DVSR
    answer += E

answer *= RWP[1]
answer %= DVSR
print(answer)

Solution (Python):
p = 1000000007
N = int(input())
T = [[] for _ in range(N)]
for _ in range(N - 1):
  (a, b) = (int(x) - 1 for x in input().split())
  T[a].append(b)
  T[b].append(a)
P = [-1] * N
P[0] = 0
Q = [0]
for i in range(N):
  q = Q[i]
  for adj in T[q]:
    if 0 <= P[adj]:
      continue
    P[adj] = q
    Q.append(adj)
ST = [[] for _ in range(N)]
for q in Q[N - 1:0:-1]:
  s = sum(ST[q]) + 1
  ST[P[q]].append(s)
  ST[q].append(N - s)
B = [1] * N
B[-1] = pow(1 << (N - 1), p - 2, p)
for i in range(N - 1, 0, -1):
  B[i - 1] = B[i] * 2 % p
H = [0] * N
ans = 0
for S in ST:
  ans += B[1] * ((1 - B[-1] - sum([(B[N - 1 - s] * (1 - B[s])) % p for s in S])) % p)
  ans %= p
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)

mod = 10 ** 9 + 7

N = int(input())
vec = [[] for _ in range(N)]
for _ in range(N - 1) :
  A, B = map(int, input().split())
  vec[A-1].append(B-1)
  vec[B-1].append(A-1)

own_size = [0] * N
sub_size = [[] for _ in range(N)]



stack = [(0, -1)]
for i in range(N) :
  cur, pre = stack[i]
  for nex in vec[cur] :
    if nex != pre :
      stack.append((nex, cur))

while stack :
  cur, pre = stack.pop()
  if pre != -1 :
    sub_size[pre].append(own_size[cur] + 1)
    own_size[pre] += own_size[cur] + 1
  if own_size[cur] != N - 1 :
    sub_size[cur].append(N - 1 - own_size[cur])

fac = [1]
inv = [1]
div = pow(2, mod - 2, mod)
for _ in range(N) :
  fac.append(fac[-1] * 2 % mod)
  inv.append(inv[-1] * div % mod)

ret = 0
for i in range(N) :
  if len(sub_size[i]) < 2 :
    continue

  a, b = 1, 1
  for ss in sub_size[i] :
    a *= inv[ss]
    b += fac[ss] - 1
    a %= mod
    b %= mod
  ret += (1 - a * b) % mod
  ret %= mod

ret = ret * div % mod

print(ret)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

mod = 10**9+7

N = int(input())
graph = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)


def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    
    return [w[0],w[1]]


def mod_inv(a,m=mod):
    x = extgcd(a,m)[0]
    return (m+x%m)%m


N2 = [1]
n = 1
for _ in range(N+1):
    n = n*2 % mod
    N2.append(n)

Weight = [[] for _ in range(N)]
checked = [False]*N

def dfs(p):
    checked[p] = True
    downs = 0
    for np in graph[p]:
        if not checked[np]:
            downscore = dfs(np)
            Weight[p].append(N-downscore)
            Weight[np].append(downscore)
            downs += N-downscore
    
    return N-(downs+1)

dfs(0)

a = 0
for n in range(N):
    if len(Weight[n]) == 1:
        continue
    c = N2[N-1] - 1
    for w in Weight[n]:
        c = (c - N2[w] + 1) % mod
    a = (a + c) % mod

ans = (a * mod_inv(N2[N])) % mod
print(ans)

Solution (Python):
N=int(input())
E=[[] for _ in range(N)]
for _ in range(N-1):
    A,B=map(int,input().split())
    E[A-1].append(B-1)
    E[B-1].append(A-1)
MOD=10**9+7


dp=[1]*N

root=0
parent=[0]*N
order=[]
def dfs():
    parent[root]=root
    stack=[root]
    while stack:
        node=stack.pop()
        order.append(node)
        for ss in E[node]:
            if parent[node]!=ss:
                stack.append(ss)
                parent[ss]=node

pow2=[1]*(N+1)
for i in range(1,len(pow2)):
    pow2[i]=pow2[i-1]*2%MOD

def solve():
    ans=0
    inv2=pow(2,MOD-2,MOD)
    
    p0=pow(pow2[N-1],MOD-2,MOD)
    for i in reversed(order):
        if root!=i:
            dp[parent[i]]+=dp[i]
        p=0
        if len(E[i])>=2:
            
            p1=1
            for s in E[i]:
                size=0
                if parent[i]!=s:
                    size=dp[s]
                elif i!=root:
                    size=N-dp[i]
                else:
                    continue
                p1+=pow2[size]-1
            p=1-(p0*p1)
            p%=MOD
        ans+=p
        ans%=MOD
    
    ans=ans*inv2%MOD
    print(ans)

dfs()
solve()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    def dfs(u=0, pu=-1):
        res = 1
        for cu in to[u]:
            if cu == pu: continue
            ret = dfs(cu, u)
            children_size[u].append(ret)
            res += ret
        return res

    md = 10 ** 9 + 7
    n = II()
    to = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = MI1()
        to[a].append(b)
        to[b].append(a)
    

    
    half = pow(2, md - 2, md)
    exp_half = [1, half]
    for _ in range(n):
        exp_half.append(exp_half[-1] * half % md)
    

    
    children_size = [[] for _ in range(n)]
    dfs()
    

    
    
    
    
    ans = 0
    noblack = exp_half[n - 1]
    for cs in children_size:
        if not cs: continue
        sum_cs = sum(cs)
        if sum_cs != n - 1: cs.append(n - 1 - sum_cs)
        onlyone = 0
        for child_size in cs:
            onlyone += (1 - exp_half[child_size]) * exp_half[n - 1 - child_size]
        ans += (1 - noblack - onlyone) * half
        ans %= md
    print(ans)

main()

Solution (Python):
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7





def div_mod(a, b, mod):
    return a * pow(b, mod - 2, mod) % mod


N = int(sys.stdin.buffer.readline())
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]













graph = [[] for _ in range(N)]
for a, b in AB:
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)



root = 0
stack = [(0, None)]
hist = []
while stack:
    v, parent = stack.pop()
    hist.append((v, parent))
    for u in graph[v]:
        if u == parent:
            continue
        stack.append((u, v))

subtree_sizes = [0] * N
hist.reverse()
for v, parent in hist:
    ret = 0
    for u in graph[v]:
        if u == parent:
            continue
        ret += subtree_sizes[u]
    subtree_sizes[v] = ret + 1

pow2 = [1]
p = 1
for _ in range(N + 10):
    p = p * 2 % MOD
    pow2.append(p)



e_exp = 0
for v in range(N):
    for u in graph[v]:
        if v < u:
            continue
        
        s = min(subtree_sizes[v], subtree_sizes[u])
        t = N - s

        
        cnt = pow2[N]
        
        cnt -= pow2[t]
        
        cnt -= pow2[s]
        
        cnt += 1
        e_exp += cnt
        e_exp %= MOD


v_exp = e_exp + pow2[N] - 1
ans = div_mod(v_exp, pow2[N], MOD) - div_mod(N, 2, MOD)
ans %= MOD
print(ans)

Solution (Python):
from collections import defaultdict,deque
mod = 10**9+7
N = int(input())
g = [[] for _ in range(N)]
d = defaultdict(lambda:-1)
p2 = [1]*(N+1)
p2[1] = pow(2,mod-2,mod)
for i in range(N):
    p2[i+1] = (p2[i]*p2[1])%mod

for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)

q = deque([[a,b]])
while q:
    i,j = q.pop()
    s = 1
    f = True
    for k in g[j]:
        if k == i:
            continue
        if (j,k) not in d:
            if f:
                q.append([i,j])
            q.append([j,k])
            f = False
        else:
            s += d[(j,k)]
    if f:
        d[(i,j)] = s

q = deque([[b,a]])
while q:
    i,j = q.pop()
    s = 1
    f = True
    for k in g[j]:
        if k == i:
            continue
        if (j,k) not in d:
            if f:
                q.append([i,j])
            q.append([j,k])
            f = False
        else:
            s += d[(j,k)]
    if f:
        d[(i,j)] = s

ans = 1-p2[N]-N*p2[1]

for i in range(N):
    for j in g[i]:
        if j<i:
            continue
        n = max(d[(i,j)],d[(j,i)])
        ans += (1-p2[n])*(1-p2[N-n])
        ans %= mod

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

mod = 10**9+7

n = int(input())
g = [[] for _ in range(n)]

pow2 = [0 for _ in range(n+1)]
pow2[0] = 1
for i in range(n):
    pow2[i+1] = pow2[i]*2 %mod

for _ in range(n-1):
    a,b = map(int, input().split())
    g[a-1].append(b-1)
    g[b-1].append(a-1)

depth = [-1]*n
ko_all = [0 for _ in range(n)]
ko_only =[0 for _ in range(n)]

def dfs(v,d):
    depth[v] = d
    for w in g[v]:
        if depth[w] == -1:
            dfs(w,d+1)
            ko_all[v] += ko_all[w]+1
            ko_only[v] += pow2[ko_all[w]+1]-1

dfs(0,0)

cnt = 0

for i in range(n):
    tmp = pow2[n-1]-1-(pow2[n-1-ko_all[i]]-1) - ko_only[i]
    tmp %=mod
    cnt += tmp
    cnt %= mod

def inv(a,mod):
    r = [1,0,a]
    w = [0,1,mod]
    while w[2]!=1:
        q = r[2]//w[2]
        r_new = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = w
        w = r_new
    x,y = w[0],w[1]    
    return (mod+x%mod)%mod

print(inv(pow2[n],mod)*cnt %mod)

Solution (Python):
import sys


def dfs1(root, links):
    parent = [0] * n
    subtree_count = [{} for _ in range(n)]
    q = [(root, -1, 0)]  
    while q:
        v, p, t = q.pop()
        if t == 0:
            parent[v] = p
            q.append((v, p, 1))
            for u in links[v]:
                if u == p:
                    continue
                q.append((u, v, 0))
        elif p != -1:
            subtree_count[p][v] = sum(subtree_count[v].values()) + 1
    return parent, subtree_count


def dfs2(root, parent, subtree_count, d2, d2s):
    ans = 0
    q = [(root, 0)]
    while q:
        v, pc = q.pop()

        if len(subtree_count[v]) == 0:
            continue

        p = parent[v]
        children, st_counts = map(list, zip(*subtree_count[v].items()))
        children.append(p)
        st_counts.append(pc)
        cl = len(st_counts)
        ct = sum(st_counts)

        for u, stc in subtree_count[v].items():
            q.append((u, ct - stc + 1))

        if cl == 1:
            continue

        tmp = 0
        for stc in st_counts:
            tmp = (tmp + d2s[ct - stc]) % MOD
        tmp = (tmp - d2s[ct] * (cl - 1)) % MOD
        ans = (ans + (1 - tmp) * d2) % MOD
    return ans


n = int(input())
links = [set() for _ in range(n)]
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
root = 0
MOD = 10 ** 9 + 7
d2 = 500000004  
d2s = [1]
for i in range(n):
    d2s.append(d2s[-1] * d2 % MOD)
parent, subtree_count = dfs1(root, links)


ans = dfs2(root, parent, subtree_count, d2, d2s)
print(ans)

Solution (Python):
import sys


def dfs1(root, links):
    parent = [0] * n
    subtree_count = [{} for _ in range(n)]
    q = [(root, -1, 0)]  
    while q:
        v, p, t = q.pop()
        if t == 0:
            parent[v] = p
            q.append((v, p, 1))
            for u in links[v]:
                if u == p:
                    continue
                q.append((u, v, 0))
        elif p != -1:
            subtree_count[p][v] = sum(subtree_count[v].values()) + 1
    return parent, subtree_count


def dfs2(root, parent, subtree_count, d2, d2s):
    ans = 0
    q = [(root, 0)]
    while q:
        v, pc = q.pop()

        if len(subtree_count[v]) == 0:
            continue

        p = parent[v]
        children, st_counts = map(list, zip(*subtree_count[v].items()))
        children.append(p)
        st_counts.append(pc)
        cl = len(st_counts)
        ct = sum(st_counts)

        for u, stc in subtree_count[v].items():
            q.append((u, ct - stc + 1))

        if cl == 1:
            continue

        tmp = 0
        for stc in st_counts:
            tmp = (tmp + d2s[ct - stc]) % MOD
        tmp = (tmp - d2s[ct] * (cl - 1)) % MOD
        ans = (ans + (1 - tmp) * d2) % MOD
    return ans


n = int(input())
links = [set() for _ in range(n)]
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
root = 0
MOD = 10 ** 9 + 7
d2 = 500000004  
d2s = [1]
for i in range(n):
    d2s.append(d2s[-1] * d2 % MOD)
parent, subtree_count = dfs1(root, links)


ans = dfs2(root, parent, subtree_count, d2, d2s)
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
N = int(input())
X = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    X[y-1].append(x-1)
i0 = min([i for i in range(N) if len(X[i]) == 1])

P = [-1] * N
Q = deque([i0])
R = []
while Q:
    i = deque.popleft(Q)
    R.append(i)
    for a in X[i]:
        if a != P[i]:
            P[a] = i
            X[a].remove(i)
            deque.append(Q, a)

mod = 10 ** 9 + 7
pow2 = [1]
for i in range(N + 10):
    pow2.append(pow2[-1] * 2 % mod)
inv2 = (mod + 1) // 2

invpow2 = [pow(pow2[-1], mod-2, mod)]
for i in range(N + 10)[::-1]:
    invpow2.append(invpow2[-1] * 2 % mod)
invpow2 = invpow2[::-1]

A = [1] * N
for i in R[::-1]:
    s = 0
    for j in X[i]:
        A[i] += A[j]

ans = 0
for i in range(N):
    s = pow(inv2, N - A[i], mod)
    t = 1 + (1-invpow2[N-A[i]]) * pow2[N-A[i]]
    for j in X[i]:
        s = (s * invpow2[A[j]]) % mod
        t = (t + (1-invpow2[A[j]]) * pow2[A[j]]) % mod
    ans = (ans + 1 - s * t) % mod

print(ans * inv2 % mod)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
N = int(input())
X = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    X[y-1].append(x-1)
i0 = min([i for i in range(N) if len(X[i]) == 1])

P = [-1] * N
Q = deque([i0])
R = []
while Q:
    i = deque.popleft(Q)
    R.append(i)
    for a in X[i]:
        if a != P[i]:
            P[a] = i
            X[a].remove(i)
            deque.append(Q, a)

mod = 10 ** 9 + 7
inv2 = (mod + 1) // 2
A = [1] * N
for i in R[::-1]:
    s = 0
    for j in X[i]:
        A[i] += A[j]

ans = 0
for i in range(N):
    s = pow(inv2, N - A[i], mod)
    t = 1 + (1-pow(inv2, N - A[i], mod)) * pow(2, N - A[i], mod)
    for j in X[i]:
        s = (s * pow(inv2, A[j], mod)) % mod
        t = (t + (1-pow(inv2, A[j], mod)) * pow(2, A[j], mod)) % mod
    ans = (ans + 1 - s * t) % mod

print(ans * inv2 % mod)