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**9)
input = sys.stdin.readline

N = int(input())
MOD = 10**9 + 7
tree = [[] for i in range(N+1)]
for i in range(N-1):
  a, b = map(int, input().split())
  tree[a].append(b)
  tree[b].append(a)


root, par = 1, 0
sizes = [0] * (N+1)
order = [[root, par]]
def calc_nums(node, par):
  global sizes
  global order
  if sizes[node] > 0:
    return sizes[node]
  children = tree[node]
  res = 1
  for child in children:
    if child == par:
      continue
    order.append([child, node])
    res += calc_nums(child, node)
  sizes[node] = res
  return res

_ = calc_nums(root, par)


prod2 = [1]
for i in range(N):
  prod2.append(prod2[-1] * 2 % MOD)


demo = 0 
div = prod2[N] 
base = prod2[N-1] - 1
for node, par in order:
  children = tree[node]
  num = base
  num_par = N - 1
  for child in children:
    if child == par:
      continue
    s = sizes[child]
    num_par -= s
    num -= prod2[s] - 1 
  num -= prod2[num_par] - 1
  demo += num
    
ans = demo * pow(div, MOD-2, MOD) % MOD
print(ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 15
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
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)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

n = I()
G = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = LI()
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]

memo = [0] * n
par = [-1] * n

def child_cnt(x):
    cnt = 1
    for y in G[x]:
        if y != par[x]:
            par[y] = x
            cnt += child_cnt(y)
    memo[x] = cnt
    return cnt

child_cnt(0)
two_mod = [1] * (n + 1)
for i in range(1, n + 1):
    two_mod[i] = two_mod[i - 1] * 2 % mod

ans = [0] * n
q = deque([0])
while q:
    u = q.pop()
    ret = two_mod[n - 1] - 1
    for v in G[u]:
        if par[u] != v:
            ret = (ret - (two_mod[memo[v]] - 1)) % mod
            q += [v]
    ret = ret - (two_mod[n - memo[u]] - 1)
    ans[u] = ret

print(sum(ans) % mod * pow(two_mod[n], mod - 2, mod) % mod)

Solution (Python):
n = int(input())
mod = 10**9 + 7


import sys
input = sys.stdin.readline
from collections import deque

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

ini = 0


def calc(a,b):
    return a+b


def calc1(c,p):
    p_num = ini
    for i in graph[c]:
        if i == p:
            continue
        p_num = calc(p_num, dp1[i])
    dp1[c] = (p_num+1) % mod


def calc2(p):
    arr = [dp1[c] if c != parent[p] else dp2[p] for c in graph[p]]

    left = [ini]
    for i in arr[:-1]:
        left.append( calc(left[-1], i ) )
    right = [ini]
    for i in arr[:0:-1]:
        right.append( calc(right[-1], i) )
    right = right[::-1]

    prod = []
    for a,b in zip(left,right):
        prod.append( calc(a,b) )

    for c,x in zip(graph[p], prod):
        if(c != parent[p]):
            dp2[c] = (x + 1) % mod



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


dp1 = [0] * (n+1)
for i in order[::-1]:
    calc1(i, parent[i])


dp2 = [0] * (n+1)
for i in order:
    calc2(i)

ans = 0
for i in range(1,n+1):
    gr = graph[i]
    if(len(gr) == 1):
        continue
    tmp = pow(2,n-1,mod) - 1
    for v in gr:
        if(v == parent[i]):
            exp_num = dp2[i]
        else:
            exp_num = dp1[v]
        tmp = (tmp - (pow(2, exp_num, mod)-1)) % mod
    ans = (ans + tmp) % mod


ans = ans * pow(pow(2,n,mod), mod-2, mod) % mod
print(ans)

Solution (Python):
import sys
import heapq as h

input=sys.stdin.readline

N=int(input())
hen=[[] for i in range(0,N)]
for i in range(0,N-1):
    a,b=map(int,input().split())
    hen[a-1].append(b-1)
    hen[b-1].append(a-1)
mod=10**9+7

subtreesize=[1 for i in range(0,N)]
flag=[0 for i in range(0,N)]
q=[]
for i in range(1,N):
    if len(hen[i])==1:
        q.append(i)
        flag[i]=0

h.heapify(q)
sub=[]
h.heapify(sub)
while q!=[]:
    while q!=[]:
        x=h.heappop(q)
        for p in hen[x]:
            if p!=0:
                if flag[p]!=len(hen[p])-1:
                    subtreesize[p]+=subtreesize[x]
                    flag[p]+=1
                    if flag[p]==len(hen[p])-1:
                        h.heappush(sub,p)
            else:
                subtreesize[p]+=subtreesize[x]
        
        
        if q==[]:
            q=sub
            sub=[]
            h.heapify(sub)
            break

ans=[0 for i in range(0,N)]
flag=[0 for i in range(0,N)]
q=[]
for i in range(1,N):
    if len(hen[i])==1:
        q.append(i)
        flag[i]=0

h.heapify(q)
sub=[]
h.heapify(sub)
while q!=[]:
    while q!=[]:
        x=h.heappop(q)
        for p in hen[x]:
            if p!=0:
                if flag[p]!=len(hen[p])-1:
                    ans[p]=(ans[p]+ans[x]-pow(2,subtreesize[x],mod)+1)%mod
                    flag[p]+=1
                    if flag[p]==len(hen[p])-1:
                        ans[p]=(ans[p]+pow(2,N-1,mod)-pow(2,N-subtreesize[p],mod))%mod
                        h.heappush(sub,p)
            else:
                ans[p]=(ans[p]+ans[x]-pow(2,subtreesize[x],mod)+1)%mod
        
        
        if q==[]:
            q=sub
            sub=[]
            h.heapify(sub)
            break


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

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

def main():
  MOD = 10**9+7
  n = int(input())
  T = [[] for _ in range(n)]
  for _ in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    T[a].append(b)
    T[b].append(a)
  C = [[] for _ in range(n)]
  seen = [False]*n
  dp = [0]*n
  def dfs(v):
    cnt = 1
    seen[v] = True
    for nv in T[v]:
      if seen[nv]:
        continue
      C[v].append(nv)
      cnt += dfs(nv)
    dp[v] = cnt
    return cnt

  dfs(0)

  p = [1]*(n+1)
  inv = [1]*(n+1)
  inv_two = pow(2, MOD-2, MOD)
  for i in range(n):
    p[i+1] = p[i] * 2 % MOD
    inv[i+1] = inv[i] * inv_two % MOD
  ans = 0
  for i in range(n):
    s = 1
    t = 1
    cnt = 1
    for c in C[i]:
      l = dp[c]
      s *= inv[l]
      s %= MOD
      t += p[l] - 1
      t %= MOD
      cnt += l
    r = n - cnt
    s *= inv[r]
    s %= MOD
    t += p[r] - 1
    t %= MOD
    res = (1 - s*t) % MOD * inv_two
    res %= MOD
    ans += res
    ans %= MOD
  print(ans)

if __name__ == "__main__":
  main()

Solution (Python):






import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache





MOD = 10**9 +7
INF = float('inf')






def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr


def lcm(a, b):
    return a * b // gcd (a, b)





N = inputI()
l = inputILL(N-1)

dic = dict([(i,[]) for i in range(1,N+1)])

for i in l:
  dic[i[0]].append(i[1])
  dic[i[1]].append(i[0])


d = [[INF,i] for i in range(N+1)]
d[1][0] = 0
q = deque([1])

while q:
  x = q.popleft()
  nd = d[x][0]+1
  for nx in dic[x]:
    if nd < d[nx][0]:
      d[nx][0] = nd
      q.append(nx)


d_ = sorted(d[1:],reverse=True)
n = [1 for _ in range(N+1)]

for item in d_:
  depth = item[0]
  i = item[1]
  for j in dic[i]:
    if d[j][0] == depth+1:
      n[i] += n[j]

ans = (pow(2,N,MOD)-N*pow(2,N-1,MOD)-1)%MOD
for i in range(2,N+1):
  ans = (ans + (pow(2,n[i],MOD)-1) * (pow(2,N-n[i],MOD)-1)) % MOD

print((ans*inv(pow(2,N,MOD)))%MOD)

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
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)
    d = [0]*n
    d[0] = 1
    q = deque([0])
    p = [None]*n
    while q:
        x = q.popleft()
        nd = d[x]+1
        for y in v[x]:
            if not d[y]:
                d[y] = nd
                p[y] = x
                q.append(y)
    V = list(range(n))
    V.sort(key = lambda x:-d[x])
    t = [1]*n
    for x in V[:-1]:
        t[p[x]] += t[x]
    ans = n
    for x in range(n):
        tx = t[x]
        for y in v[x]:
            ty = t[y]
            if tx < ty:
                ans += pow(2,t[0]-tx,mod)-1
            else:
                ans += pow(2,ty,mod)-1
        ans %= mod
    print((n*pow(2,mod-2,mod)-ans*pow(2,(mod-2)*n%(mod-1),mod))%mod)
    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
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)
    d = [0]*n
    d[0] = 1
    q = deque([0])
    p = [None]*n
    while q:
        x = q.popleft()
        nd = d[x]+1
        for y in v[x]:
            if not d[y]:
                d[y] = nd
                p[y] = x
                q.append(y)
    V = list(range(n))
    V.sort(key = lambda x:-d[x])
    t = [1]*n
    for x in V[:-1]:
        t[p[x]] += t[x]
    ans = n
    for x in range(n):
        tx = t[x]
        s = 0
        for y in v[x]:
            ty = t[y]
            if tx < ty:
                s += pow(2,t[0]-tx,mod)-1
            else:
                s += pow(2,ty,mod)-1
            s %= mod
        ans += s
        ans %= mod
    print((n*pow(2,mod-2,mod)-ans*pow(2,(mod-2)*n%(mod-1),mod))%mod)
    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
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)
    d = [0]*n
    d[0] = 1
    q = deque([0])
    p = [None]*n
    while q:
        x = q.popleft()
        nd = d[x]+1
        for y in v[x]:
            if not d[y]:
                d[y] = nd
                p[y] = x
                q.append(y)
    V = list(range(n))
    V.sort(key = lambda x:-d[x])
    t = [1]*n
    for x in V[:-1]:
        t[p[x]] += t[x]
    ans = 0
    p = pow(2,n-1,mod)
    for x in range(n):
        tx = t[x]
        if len(v[x]) < 2:
            continue
        s = p-1
        for y in v[x]:
            ty = t[y]
            if tx < ty:
                s -= pow(2,t[0]-tx,mod)-1
            else:
                s -= pow(2,ty,mod)-1
            s %= mod
        ans += s
        ans %= mod
    print(ans*pow(2,(mod-2)*n%(mod-1),mod)%mod)
    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
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)
    d = [0]*n
    d[0] = 1
    q = deque([0])
    p = [None]*n
    while q:
        x = q.popleft()
        nd = d[x]+1
        for y in v[x]:
            if not d[y]:
                d[y] = nd
                p[y] = x
                q.append(y)
    V = list(range(n))
    V.sort(key = lambda x:-d[x])
    t = [1]*n
    for x in V[:-1]:
        t[p[x]] += t[x]
    ans = 0
    p = pow(2,n-1,mod)
    for x in range(n):
        tx = t[x]
        if len(v[x]) < 2:
            continue
        s = p-1
        for y in v[x]:
            ty = t[y]
            if tx < ty:
                s -= pow(2,t[0]-tx,mod)-1
            else:
                s -= pow(2,ty,mod)-1
            s %= mod
        ans += s
        ans %= mod
    print(ans*pow(2,(mod-2)*n%(mod-1),mod)%mod)
    return


if __name__ == "__main__":
    solve()

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

depth[0] = 0
stack = [0]

while stack:
    v = stack.pop()
    if any(depth[w] == -1 for w in g[v]):
        stack.append(v)
    for w in g[v]:
        if depth[w] == -1:
            depth[w] = depth[v] + 1
            stack.append(w)
        elif depth[w] > depth[v]:
            ko_all[v] += ko_all[w] + 1
            ko_only[v] += pow2[ko_all[w]+1]-1


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
input=lambda: sys.stdin.readline().rstrip()
mod=10**9+7
n=int(input())
edge=[[] for i in range(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)
inf=10**6
Par=[inf]*n
Par[0]=-1
Deg=[0]*n
Deg[0]=0
Chk=[0]
while Chk:
  c=Chk.pop()
  for next in edge[c]:
    if Par[next]==inf:
      Par[next]=c
      Deg[next]+=1
      Chk.append(next)

from collections import deque
TS=list(v for v in range(n) if Deg[v]==0)
D=deque(TS)
while D:
  v=D.popleft()
  for t in edge[v]:
    if t!=Par[v]:
      Deg[t]-=1
      if Deg[t]==0:
        D.append(t)
        TS.append(t)

Used=[False]*n
C=[0]*n
for i in reversed(range(n)):
  v=TS[i]
  Used[v]=True
  for g in edge[v]:
    if not Used[g]:
      C[g]+=C[v]+1

H=[0]*n
H[0]=1
H[1]=pow(2,mod-2,mod)
for i in range(2,n):
  H[i]=(H[i-1]*H[1])%mod

ans=0
for i in range(n):
  if len(edge[i])==1:
    continue
  else:
    A=[]
    for e in edge[i]:
      if e==Par[i]:
        A.append(n-1-C[i])
      else:
        A.append(C[e]+1)
    cur=1+(len(edge[i])-1)*H[-1]
    for a in A:
      cur-=H[n-1-a]
    ans+=cur
print((ans*H[1])%mod)

Solution (Python):
import sys
input=lambda: sys.stdin.readline().rstrip()
mod=10**9+7
n=int(input())
edge=[[] for i in range(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)
inf=10**6
Par=[inf]*n
Par[0]=-1
Deg=[0]*n
Deg[0]=0
Chk=[0]
while Chk:
  c=Chk.pop()
  for next in edge[c]:
    if Par[next]==inf:
      Par[next]=c
      Deg[next]+=1
      Chk.append(next)

from collections import deque
TS=list(v for v in range(n) if Deg[v]==0)
D=deque(TS)
while D:
  v=D.popleft()
  for t in edge[v]:
    if t!=Par[v]:
      Deg[t]-=1
      if Deg[t]==0:
        D.append(t)
        TS.append(t)

Used=[False]*n
C=[0]*n
for i in reversed(range(n)):
  v=TS[i]
  Used[v]=True
  for g in edge[v]:
    if not Used[g]:
      C[g]+=C[v]+1

H=[0]*n
H[0]=1
H[1]=pow(2,mod-2,mod)
for i in range(2,n):
  H[i]=(H[i-1]*H[1])%mod

ans=0
for i in range(n):
  if len(edge[i])==1:
    continue
  else:
    A=[]
    for e in edge[i]:
      if e==Par[i]:
        A.append(n-1-C[i])
      else:
        A.append(C[e]+1)
    cur=1+(len(edge[i])-1)*H[-1]
    for a in A:
      cur-=H[n-1-a]
    ans=(ans+cur)%mod
print((ans*H[1])%mod)

Solution (Python):
import sys
input=lambda: sys.stdin.readline().rstrip()
mod=10**9+7
n=int(input())
edge=[[] for i in range(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)
inf=10**6
Par=[inf]*n
Par[0]=-1
Deg=[0]*n
Deg[0]=0
Chk=[0]
while Chk:
  c=Chk.pop()
  for next in edge[c]:
    if Par[next]==inf:
      Par[next]=c
      Deg[next]+=1
      Chk.append(next)

from collections import deque
TS=list(v for v in range(n) if Deg[v]==0)
D=deque(TS)
while D:
  v=D.popleft()
  for t in edge[v]:
    if t!=Par[v]:
      Deg[t]-=1
      if Deg[t]==0:
        D.append(t)
        TS.append(t)

Used=[False]*n
C=[0]*n
for i in reversed(range(n)):
  v=TS[i]
  Used[v]=True
  for g in edge[v]:
    if not Used[g]:
      C[g]+=C[v]+1

H=[0]*n
H[0]=1
H[1]=pow(2,mod-2,mod)
for i in range(2,n):
  H[i]=(H[i-1]*H[1])%mod

ans=0
for i in range(n):
  if len(edge[i])==1:
    continue
  else:
    A=[]
    for e in edge[i]:
      if e==Par[i]:
        A.append(n-1-C[i])
      else:
        A.append(C[e]+1)
    cur=1+(len(edge[i])-1)*H[-1]
    for a in A:
      cur-=H[n-1-a]
    ans=(ans+cur)%mod
print((ans*H[1])%mod)

Solution (Python):
n = int(input())
G = [[] for _ in range(n)]
mod = 10**9 + 7

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

stack = [0]
depth = [-1] * n
depth[0] = 0
while stack:
    v = stack.pop()
    d = depth[v]
    for nv in G[v]:
        if depth[nv] >= 0:continue
        depth[nv] = depth[v] + 1
        stack.append(nv)

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

for i in range(n):
    d_to_i[depth[i]].append(i)

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

for d in range(n-1, -1, -1):
    for v in d_to_i[d]:
        for nv in G[v]:
            if depth[nv] < depth[v]:
                continue
            if data[nv]:
                data[v].append(n-data[nv][-1])
        if data[v]:
            data[v].append(n - 1- sum(data[v]))
        else:
            data[v].append(n - 1)

ans = 0
two = [1]
for i in range(n):
    two.append(two[-1] * 2 % mod)
for i in range(n):
    now = two[n-1]-1
    for x in data[i]:
        now -= two[x]-1
        now %= mod
    ans += now


ans *= pow(two[n], mod-2, mod)
ans %= mod
print(ans)

Solution (Python):
import sys
input=lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(200000)
mod=10**9+7
n=int(input())
edge=[[] for i in range(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)
inf=10**6
Par=[inf]*n
Par[0]=-1
Chk=[0]
while Chk:
  c=Chk.pop()
  for next in edge[c]:
    if Par[next]==inf:
      Par[next]=c
      Chk.append(next)

C=[-1]*n
def ch(x):
  ret=0
  if x!=0 and len(edge[x])==1:
    C[x]=0
    return C[x]
  else:
    for e in edge[x]:
      if e==Par[x]:
        continue
      else:
        ret+=ch(e)+1
    C[x]=ret
    return C[x]
ch(0)

H=[0]*n
H[0]=1
H[1]=pow(2,mod-2,mod)
for i in range(2,n):
  H[i]=(H[i-1]*H[1])%mod

ans=0
for i in range(n):
  if len(edge[i])==1:
    continue
  else:
    A=[]
    for e in edge[i]:
      if e==Par[i]:
        A.append(n-1-C[i])
      else:
        A.append(C[e]+1)
    cur=1+(len(edge[i])-1)*H[-1]
    for a in A:
      cur-=H[n-1-a]
    ans=(ans+cur)%mod
print((ans*H[1])%mod)

Solution (Python):

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
MOD = 10**9+7

def main():
    N = int(readline())
    m = map(int,read().split())
    AB = zip(m,m)
    graph = [[] for _ in range(N+1)]
    
    for a,b in AB:
        graph[a].append(b)
        graph[b].append(a)
    
    root = 1 
    stack = [root] 
    parent = [0]*(N+1) 
    order = [] 
    while stack: 
        node = stack.pop()
        order.append(node)
        for child in graph[node]:
            if parent[node] == child:
                continue
            parent[child] = node
            stack.append(child)
    

    pow_inv = [1]*(N+1) 
    for i in range(N):
        pow_inv[i+1] = pow_inv[i]*2%MOD
    
    
    node_count = [1]*(N+1)
    for v in order[::-1]:
        node_count[parent[v]] += node_count[v]
    
    tmp = 0 
    for target_node in range(1,N+1): 
        child_par_sum = 0

        for child in graph[target_node]:
            if child == parent[target_node]:
                continue
            child_par_sum += node_count[child]
            tmp += pow_inv[node_count[child]]-1
        parent_par_sum = N-1-child_par_sum
        tmp += pow_inv[parent_par_sum]-1
        tmp%=MOD
    
    y = (pow_inv[N-1]-1)*N-tmp
    y %= MOD
    x = pow(pow_inv[N],MOD-2,MOD)
    z = x*y%MOD
    print(z)
    return

if __name__ == '__main__':
    main()