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 os
import sys
import numpy as np

def solve(N, AB):
    mod = 10**9+7
    half = mod // 2 + 1
    G = [[0]*0 for _ in range(N+1)]
    for i in range(len(AB)):
        a, b = AB[i]
        G[a].append(b)
        G[b].append(a)
    P = np.zeros(N+1, dtype=np.int64)
    Size = np.zeros(N+1, dtype=np.int64)
    def dfs(v):
        
        
        
        
        
        
        
        
        st = [(v, 0)]
        while st:
            v, state = st.pop()
            p = P[v]
            if state == 0:
                st.append((v, 1))
                Size[v] = 1
                for u in G[v]:
                    if u != p:
                        P[u] = v
                        st.append((u, 0))
            else:
                Size[p] += Size[v]
    dfs(1)
    ans = 0
    Prob = np.empty(202020, dtype=np.int64)
    h = 1
    for i in range(202020):
        Prob[i] = 1-h+mod
        h = h * half % mod
    for v in range(1, len(G)):
        siz_v = Size[v]
        Gv = G[v]
        if v == 1:
            ps = [0]*0
        else:
            ps = [Prob[N-siz_v]]
        par = P[v]
        for u in Gv:
            if par != u:
                siz_u = Size[u]
                ps.append(Prob[siz_u])
        if len(ps)<=1:
            continue
        cumprod1_ps = [1, 1]
        cumprod2_ps = [1, 1]
        cp = 1
        for p in ps:
            cp = cp * (1-p+mod) % mod
            cumprod1_ps.append(cp)
        cp = 1
        for p in ps[::-1]:
            cp = cp * (1-p+mod) % mod
            cumprod2_ps.append(cp)
        cumprod2_ps.reverse()
        an = 1 - cumprod1_ps[-1]
        for j in range(1, len(cumprod1_ps)-1):
            cp1 = cumprod1_ps[j]
            cp2 = cumprod2_ps[j]
            p = ps[j-1]
            an -= cp1 * cp2 % mod * p % mod
        ans += an
    ans = ans % mod * half % mod
    return ans



numba_config = [
    [solve, "i8(i8,i8[:,:])"],
]
if sys.argv[-1] == "ONLINE_JUDGE":
    from numba import njit
    from numba.pycc import CC
    cc = CC("my_module")
    for func, signature in numba_config:
        vars()[func.__name__] = njit(signature)(func)
        cc.export(func.__name__, signature)(func)
    cc.compile()
    exit()
elif os.name == "posix":
    exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
else:
    from numba import njit
    for func, signature in numba_config:
        vars()[func.__name__] = njit(signature, cache=True)(func)
    print("compiled!", file=sys.stderr)



def main():
    sys.setrecursionlimit(505050)
    input = sys.stdin.buffer.readline
    N = int(input())
    AB = np.array(sys.stdin.buffer.read().split(), dtype=np.int64).reshape(N - 1, 2)
    ans = solve(N, AB)
    print(ans)

main()

Solution (Python):
import os
import sys
import numpy as np

def solve(N, AB):
    mod = 10**9+7
    half = mod // 2 + 1
    G = [[0]*0 for _ in range(N+1)]
    for i in range(len(AB)):
        a, b = AB[i]
        G[a].append(b)
        G[b].append(a)
    P = [0] * (N+1)
    Size = [0] * (N+1)
    def dfs(v):
        
        
        
        
        
        
        
        
        st = [(v, 0)]
        while st:
            v, state = st.pop()
            p = P[v]
            if state == 0:
                st.append((v, 1))
                Size[v] = 1
                for u in G[v]:
                    if u != p:
                        P[u] = v
                        st.append((u, 0))
            else:
                Size[p] += Size[v]
    dfs(1)
    ans = 0
    Prob = [0]
    h = 1
    for i in range(202020):
        h = h * half % mod
        Prob.append(1-h)
    for v in range(1, len(G)):
        siz_v = Size[v]
        Gv = G[v]
        if v == 1:
            ps = [0]*0
        else:
            ps = [Prob[N-siz_v]]
        par = P[v]
        for u in Gv:
            if par != u:
                siz_u = Size[u]
                ps.append(Prob[siz_u])
        if len(ps)<=1:
            continue
        cumprod1_ps = [1, 1]
        cumprod2_ps = [1, 1]
        cp = 1
        for p in ps:
            cp = cp * (1-p) % mod
            cumprod1_ps.append(cp)
        cp = 1
        for p in ps[::-1]:
            cp = cp * (1-p) % mod
            cumprod2_ps.append(cp)
        cumprod2_ps.reverse()
        an = 1 - cumprod1_ps[-1]
        for j in range(1, len(cumprod1_ps)-1):
            cp1 = cumprod1_ps[j]
            cp2 = cumprod2_ps[j]
            p = ps[j-1]
            an -= cp1 * cp2 % mod * p
        ans += an
    ans = ans % mod * half % mod
    return ans


def main():
    sys.setrecursionlimit(505050)
    input = sys.stdin.buffer.readline
    N = int(input())
    AB = np.array(sys.stdin.buffer.read().split(), dtype=np.int64).reshape(N - 1, 2)
    ans = solve(N, AB)
    print(ans)

main()

Solution (Python):
import sys
sys.setrecursionlimit(505050)
input = sys.stdin.buffer.readline
N = int(input())
AB = [list(map(int, input().split())) for _ in range(N-1)]
mod = 10**9+7
half = mod // 2 + 1
G = [[] for _ in range(N+1)]
for a, b in AB:
    G[a].append(b)
    G[b].append(a)
P = [0] * (N+1)
Size = [0] * (N+1)
def dfs(v):
    siz = 1
    p = P[v]
    for u in G[v]:
        if u != p:
            P[u] = v
            dfs(u)
            siz += Size[u]
    Size[v] = siz
dfs(1)
ans = 0
Prob = [0]
h = 1
for i in range(202020):
    h = h * half % mod
    Prob.append(1-h)
for v, (siz_v, Gv) in enumerate(zip(Size[1:], G[1:]), 1):
    if v == 1:
        ps = []
    else:
        ps = [Prob[N-siz_v]]
    par = P[v]
    for u in Gv:
        if par != u:
            siz_u = Size[u]
            ps.append(Prob[siz_u])
    if len(ps)<=1:
        continue
    cumprod1_ps = [1, 1]
    cumprod2_ps = [1, 1]
    cp = 1
    for p in ps:
        cp = cp * (1-p) % mod
        cumprod1_ps.append(cp)
    cp = 1
    for p in ps[::-1]:
        cp = cp * (1-p) % mod
        cumprod2_ps.append(cp)
    cumprod2_ps.reverse()
    an = 1 - cumprod1_ps[-1]
    for cp1, cp2, p in zip(cumprod1_ps[1:-1], cumprod2_ps[1:-1], ps):
        an -= cp1 * cp2 % mod * p
    ans += an
ans = ans % mod * half % mod
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 6)

LI = lambda: list(map(int, input().split()))

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

link = [[] for _ in range(N)]
children = [[] for _ in range(N)]
w = [1] * N
visit = [False] * N

MOD = 10 ** 9 + 7


def create_link():
    for a, b in AB:
        link[a - 1].append(b - 1)
        link[b - 1].append(a - 1)


def dfs(s):
    visit[s] = True
    for t in link[s]:
        if visit[t]:
            continue
        children[s].append(t)
        dfs(t)
        w[s] += w[t]


def modinv(x):
    return pow(x, MOD - 2, MOD)


def main():
    create_link()
    dfs(0)
    p2 = [None] * (N + 1)
    p2[0] = 1
    for i in range(N):
        p2[i + 1] = 2 * p2[i] % MOD
    
    x = 0
    for i in range(N):
        s = p2[N - w[i]]
        for j in children[i]:
            s = (s + p2[w[j]] - 1) % MOD
        x = (x + p2[N - 1] - s) % MOD
    y = p2[N]

    ans = x * modinv(y) % MOD
    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
MOD=10**9+7
N=int(input())

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


def dfs(u,par):
  visited[u]=True
  ret=1
  for v in tree[u]:
    if not visited[v]:
      ret+=dfs(v,u)

  if par>0:
    tree_dic[(u,par)]=ret
  return ret
  
visited=[False]*(N+1)
tree_dic={}
dfs(1,0)


bumbo=pow(2,N,MOD)
bunshi=(pow(2,N,MOD)-1-N*pow(2,N-1,MOD))%MOD
for x in tree_dic.values():
  term=(pow(2,x,MOD)-1)*(pow(2,N-x,MOD)-1)
  bunshi+=term  
  bunshi%=MOD


answer=bunshi*pow(bumbo,MOD-2,MOD)
answer%=MOD
print(answer)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

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

def dfs(v, p=-1):
  global ans

  res = 1
  ts = []
  for u in adj[v]:
    if (u==p): continue
    t = dfs(u,v)
    res += t
    ts.append(t)

  if p != -1:
    ts.append(N-res)

  

  
  now = pows[N-1]-1
  for t in ts:
    
    now -= pows[t] - 1
  ans += now
  return res

ans = 0
MOD = 10**9+7

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

dfs(1)
print((ans * pow(pows[N], MOD-2, MOD)) % MOD)

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
mod = 10**9 + 7
N = int(input())
G = [[] for i in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
S = -1
for i in range(1, N+1):
    if len(G[i]) == 1:
        S = i
        break
visited = [False for i in range(N+1)]
parent = [-1 for i in range(N+1)]
count = [1 for i in range(N+1)]

ans = N*pow(2, N-1, mod)


def dfs(node):
    visited[node] = True
    for child in G[node]:
        if visited[child] == False:
            parent[child] = node
            dfs(child)
    for child in G[node]:
        if child != parent[node]:
            count[node] += count[child]


powers = [1 for i in range(2*10**5+1)]
for i in range(1, 2*10**5+1):
    powers[i] = powers[i-1]*2 % mod

dfs(S)

ans = 0
for i in range(1, N+1):
    if len(G[i]) > 1:
        ans += powers[N-1]
        for x in G[i]:
            if x != parent[i]:
                ans -= powers[count[x]]
        ans -= powers[N-count[i]]
        ans += len(G[i]) - 1
        ans %= mod
D = pow(2, N, mod)
print(ans*pow(D, mod-2, mod) % mod)

Solution (Python):

from collections import deque
import sys
sys.setrecursionlimit(10**8)
mod = 10**9 + 7
N = int(input())
G = [[] for i in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)
S = -1
for i in range(1, N+1):
    if len(G[i]) == 1:
        S = i
        break
visited = [False for i in range(N+1)]
parent = [-1 for i in range(N+1)]
count = [1 for i in range(N+1)]

ans = N*pow(2, N-1, mod)
stack = deque()


def dfs(node):
    visited[node] = True
    for child in G[node]:
        if visited[child] == False:
            parent[child] = node
            stack.append((node, child))
            dfs(child)


powers = [1 for i in range(2*10**5+1)]
for i in range(1, 2*10**5+1):
    powers[i] = powers[i-1]*2 % mod

dfs(S)
while stack:
    mom, child = stack.pop()
    count[mom] += count[child]
ans = 0
for i in range(1, N+1):
    if len(G[i]) > 1:
        ans += powers[N-1]
        for x in G[i]:
            if x != parent[i]:
                ans -= powers[count[x]]
        ans -= powers[N-count[i]]
        ans += len(G[i]) - 1
        ans %= mod
D = pow(2, N, mod)
print(ans*pow(D, mod-2, mod) % mod)

Solution (Python):
import sys
import itertools

import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines



MOD = 10 ** 9 + 7
def my_pow(base, n, mod):
    if n == 0:
        return 1
    x = base
    y = 1
    while n > 1:
        if n % 2 == 0:
            x *= x
            n //= 2
        else:
            y *= x
            n -= 1
        x %= mod
        y %= mod
    return x * y % mod

N = int(input())

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

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

ans = 0
def dfs(v, p):
    global ans
    subs = []
    res = 1
    for u in adj[v]:
        if u == p:
            continue
        val = dfs(u, v)
        res += val
        subs.append(val)
    
    if p != -1:
        subs.append(N - res)
    now = pows[N - 1] - 1 
    for sub in subs:
        now -= pows[sub] - 1
    ans += now
    ans %= MOD
    return res

dfs(0, -1)
print(ans * my_pow(2 ** N, MOD - 2, MOD) % MOD)

Solution (Python):
def main():
    import sys
    input = lambda : sys.stdin.readline().rstrip()
    sys.setrecursionlimit(max(1000, 10**9))
    write = lambda x: sys.stdout.write(x+"\n")


    

    
    from collections import defaultdict
    
    
    n = int(input())
    ns = defaultdict(set)
    for _ in range(n-1):
        u,v = map(int, input().split())
        u -= 1
        v -= 1
        ns[u].add(v)
        ns[v].add(u)


    
    def dfs(start):
        q = [start]
        
        seen = [None]*n
        
        done = [None]*n
        parent = [None]*n
        parent[start] = -1
        d0 = 0
        d1 = n
        while q:
            u = q.pop()
            if u>=0:
                if seen[u] is not None:
                    continue
                seen[u] = d0
                d0 += 1
                q.append(~u)
                for v in ns[u]:
                    if seen[v] is None:
                        q.append(v)
                        parent[v] = u
            else:
                d1 -= 1
                done[~u] = d1
        return seen, done, parent
    seen, done, parent = dfs(0)
    done = [(u,d) for u,d in enumerate(done)]
    done.sort(key = lambda x: -x[1])
    bs = {}
    for u,_ in done:
        val = 1
        p = parent[u]
        for v in ns[u]:
            if v!=p:
                val += bs[u,v]
        bs[p,u] = val

    bs[0,-1] = 0
    for u,_ in reversed(done):
        p = parent[u]
        for v in ns[u]:
            if v==p:
                continue
            b1 = bs[p,u]
            b2 = bs[u,v]
            b3 = bs[u,p]
            
            bb = b1 - b2 + b3
            bs[v,u] = bb

    M = 10**9 + 7
    p1 = pow(2, n-1, M)
    p2 = pow(2, n, M)
    p3 = pow(p2, M-2, M)
    ans = 0
    for u in range(n):
        s = 0
        for v in ns[u]:
            s += pow(2, bs[u,v], M) - 1
            s %= M
        val = p1 - s - 1
        ans += val
        ans %= M
    ans *= p3
    ans %= M
    print(ans%M)
main()

Solution (Python):
def main():
    import sys
    input = lambda : sys.stdin.readline().rstrip()
    sys.setrecursionlimit(max(1000, 10**9))
    write = lambda x: sys.stdout.write(x+"\n")


    

    
    from collections import defaultdict
    
    
    n = int(input())
    ns = defaultdict(set)
    for _ in range(n-1):
        u,v = map(int, input().split())
        u -= 1
        v -= 1
        ns[u].add(v)
        ns[v].add(u)


    
    def dfs(start):
        q = [start]
        
        seen = [None]*n
        
        done = [None]*n
        parent = [None]*n
        parent[start] = -1
        d0 = 0
        d1 = n
        while q:
            u = q.pop()
            if u>=0:
                if seen[u] is not None:
                    continue
                seen[u] = d0
                d0 += 1
                q.append(~u)
                for v in ns[u]:
                    if seen[v] is None:
                        q.append(v)
                        parent[v] = u
            else:
                d1 -= 1
                done[~u] = d1
        return seen, done, parent
    seen, done, parent = dfs(0)
    done = [(u,d) for u,d in enumerate(done)]
    done.sort(key = lambda x: -x[1])
    bs = {}
    for u,_ in done:
        p = parent[u]
        bs[p,u] = 1 + sum(bs[u,v] for v in ns[u] if v!=p)

    bs[0,-1] = 0
    for u,_ in reversed(done):
        p = parent[u]
        for v in ns[u]:
            if v==p:
                continue
            bs[v,u] = bs[p,u] - bs[u,v] + bs[u,p]

    M = 10**9 + 7
    p1 = pow(2, n-1, M)
    p2 = pow(2, n, M)
    p3 = pow(p2, M-2, M)
    ans = 0
    for u in range(n):
        s = 0
        for v in ns[u]:
            s += pow(2, bs[u,v], M) - 1
            s %= M
        val = p1 - s - 1
        ans += val
        ans %= M
    ans *= p3
    ans %= M
    print(ans%M)





main()

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(readline())
m = map(int,read().split())
AB = zip(m,m)

MOD = 10 ** 9 + 7

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 = (MOD + 1) // 2
power = [1] * (N+100)
power_inv = [1] * (N+100)
for i in range(1,N+100):
    power[i] = power[i-1] * 2 % MOD
    power_inv[i] = power_inv[i-1] * x % MOD


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 *= power_inv[x]
        prod %= MOD
        coef += (power[x] - 1)
    E = 1 - prod * coef % MOD
    answer += E

answer *= power_inv[1]
answer %= MOD
print(answer)

Solution (Python):
import sys
input = sys.stdin.readline
N = int(input())
mod = 10 ** 9 + 7
e = [[] for _ in range(N + 1)]
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)

s = [1]
order = []
parent = [0] * (N + 1)
size = [1] * (N + 1)
vis = [0] * (N + 1)
while len(s):
  x = s.pop()
  order.append(x)
  vis[x] = 1
  for y in e[x]:
    if vis[y]: continue
    s.append(y)
    vis[y] = 1
    parent[y] = x

order.reverse()
for y in order[: -1]: size[parent[y]] += size[y]


rev = lambda x: pow(x, mod - 2, mod)
res = rev(2) - rev(pow(2, N, mod))
res %= mod
for y in e[1]:
  res -= rev(pow(2, N - size[y], mod)) * (1 - rev(pow(2, size[y], mod)))
  res %= mod


order.reverse()
for y in order[1: ]:
  t = rev(2) - rev(pow(2, N, mod))
  x = parent[y]
  
  for z in e[y]:
    if x == z: continue
    t -= rev(pow(2, N - size[z], mod)) * (1 - rev(pow(2, size[z], mod)))
    t %= mod
  
  t -= rev(pow(2, size[y], mod)) * (1 - rev(pow(2, N - size[y], mod)))
  t %= mod
  res += t
  res %= mod
  
print(res)

Solution (Python):


from collections import deque
from heapq import heappop, heappush

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


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


half = pow(2, MOD - 2, MOD)
power_inv = [1] * (N + 1)
size = [1] * (N + 1)
for i, v in enumerate(order[::-1], 1):
    p = parent[v]
    x = size[v]  
    size[p] += x  
    power_inv[i] = power_inv[i - 1] * half % MOD  





ans = sum((1 - power_inv[i] - power_inv[N - i] + power_inv[N]) %
          MOD for i in size[2:])  


ans += 1  

ans -= power_inv[N] + N * power_inv[1]  

ans %= MOD

print(ans)

Solution (Python):


from collections import deque
from heapq import heappop, heappush

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


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


half = pow(2, MOD - 2, MOD)
power_inv = [1] * (N + 1)
size = [1] * (N + 1)
for i, v in enumerate(order[::-1], 1):
    p = parent[v]
    x = size[v]  
    size[p] += x  
    power_inv[i] = power_inv[i - 1] * half % MOD  





ans = sum((1 - power_inv[i] - power_inv[N - i] + power_inv[N]) %
          MOD for i in size[2:])  


ans += 1  

ans -= power_inv[N] + N * power_inv[1]  

ans %= MOD

print(ans)

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

def solve():
    MOD = 10**9 + 7

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

    sizeSubtrees = [0] * N
    sizeAdjss = [[] for _ in range(N)]

    def dfs(vNow, vPar):
        sizeSubtrees[vNow] = 1
        for v2 in adjL[vNow]:
            if v2 == vPar: continue
            s = dfs(v2, vNow)
            sizeAdjss[vNow].append(s)
            sizeSubtrees[vNow] += s
        sizeAdjss[vNow].append(N-sizeSubtrees[vNow])
        return sizeSubtrees[vNow]

    dfs(0, -1)

    def getPows(base, n, MOD):
        pows = [1] * (n+1)
        for x in range(1, n+1):
            pows[x] = (pows[x-1] * base) % MOD
        return pows
    pow2s = getPows(2, N, MOD)

    nums = [0] * N
    for v in range(N):
        num = pow2s[N-1] - 1
        for sizeAdj in sizeAdjss[v]:
            num -= pow2s[sizeAdj] - 1
            num %= MOD
        nums[v] = num

    ans = sum(nums) % MOD * pow(pow2s[N], MOD-2, MOD) % MOD
    print(ans)


solve()

Solution (Python):
from collections import deque


def topological_sort_tree(tree: list, root) -> list:
    """根付き木をトポロジカルソートする"""
    n = len(tree)
    ans = [root]
    visited = [False] * n
    visited[root] = True
    q = deque([root])
    while q:
        par = q.popleft()
        for child in tree[par]:
            if visited[child]:
                continue
            visited[child] = True
            q.append(child)
            ans.append(child)
    return ans


n = int(input())
info = [list(map(int, input().split())) for i in range(n - 1)]
MOD = 10 ** 9 + 7


tree = [[] for i in range(n)]
for a, b in info:
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)


inv2 = pow(2, MOD - 2, MOD)
ans = 0
tp_sorted = topological_sort_tree(tree, 0)[::-1]
dp = [0] * n
for v in tp_sorted:
    sum_ = 0
    w_p = []
    for nxt_v in tree[v]:
        sum_ += dp[nxt_v]
        if dp[nxt_v] != 0:
            w_p.append(pow(inv2, dp[nxt_v], MOD))
    dp[v] = sum_ + 1

    if len(tree[v]) == 1:
        continue
    if n - dp[v] != 0:
        w_p.append(pow(inv2, n - dp[v], MOD))

    res = 1
    all_w = 1
    for val in w_p:
        all_w *= val
        all_w %= MOD
    res -= all_w
    res %= MOD

    for val in w_p:
        b = 1 - val
        res -= all_w * pow(val, MOD - 2, MOD) * b
        res %= MOD
    ans += res * inv2
    ans %= MOD

print(ans % MOD)

Solution (Python):

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

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

mod = 10**9 + 7
par = [0] * (n + 1)
order = []
stk = deque()
stk.append(1)

while stk:
    v = stk.pop()
    order.append(v)
    for x in g[v]:
        if x == par[v]:
            continue
        par[x] = v
        stk.append(x)

rev = (mod + 1) // 2
po2_inv = [1] * (n + 1)
size = [1] * (n + 1)
for i, y in enumerate(order[::-1], 1):
    p = par[y]
    size[p] += size[y]
    po2_inv[i] = po2_inv[i - 1] * rev % mod

ans = 1
for i in size[2:]:
    ans += (1 - po2_inv[i] - po2_inv[n - i] + po2_inv[n]) % mod
ans -= po2_inv[n] + n * po2_inv[1]
ans %= mod
print(ans)

Solution (Python):

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

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

mod = 10**9 + 7
par = [0] * (n + 1)
order = []
stk = deque()
stk.append(1)

while stk:
    v = stk.pop()
    order.append(v)
    for x in g[v]:
        if x == par[v]:
            continue
        par[x] = v
        stk.append(x)

rev = pow(2, mod - 2, mod)
po2_inv = [1] * (n + 1)
size = [1] * (n + 1)
for i, y in enumerate(order[::-1], 1):
    p = par[y]
    size[p] += size[y]
    po2_inv[i] = po2_inv[i - 1] * rev % mod

ans = 1
for i in size[2:]:
    ans += (1 - po2_inv[i] - po2_inv[n - i] + po2_inv[n]) % mod
ans -= po2_inv[n] + n * po2_inv[1]
ans %= mod
print(ans)

Solution (Python):
import sys
from collections import deque

read = sys.stdin.buffer.read


def main():
    MOD = 1000000007
    N, *AB = map(int, read().split())
    G = [[] for _ in range(N)]
    for a, b in zip(AB[::2], AB[1::2]):
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)

    stack = deque([0])
    order = []
    prev = [0] * N
    prev[0] = -1
    while stack:
        v = stack.pop()
        order.append(v)
        for nv in G[v]:
            if nv != prev[v]:
                stack.append(nv)
                prev[nv] = v

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

    nodes = [1] * N
    numer = 0

    for v in reversed(order):
        if prev[v] != -1:
            nodes[prev[v]] += nodes[v]
        numer = (numer + pow2[N - 1] - pow2[N - nodes[v]]) % MOD
        for nv in G[v]:
            if nv != prev[v]:
                numer = (numer - pow2[nodes[nv]] + 1) % MOD

    denom = pow2[N]
    ans = (numer * pow(denom, MOD - 2, MOD)) % MOD
    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque

read = sys.stdin.buffer.read


def main():
    MOD = 1000000007
    N, *AB = map(int, read().split())
    G = [[] for _ in range(N)]
    for a, b in zip(AB[::2], AB[1::2]):
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)

    stack = deque([0])
    order = []
    prev = [0] * N
    prev[0] = -1
    while stack:
        v = stack.pop()
        order.append(v)
        for nv in G[v]:
            if nv != prev[v]:
                stack.append(nv)
                prev[nv] = v

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

    nodes = [1] * N
    numer = 0

    for v in reversed(order):
        if prev[v] != -1:
            nodes[prev[v]] += nodes[v]
        numer = (numer + pow2[N - 1] - pow2[N - nodes[v]]) % MOD
        for nv in G[v]:
            if nv != prev[v]:
                numer = (numer - pow2[nodes[nv]] + 1) % MOD

    denom = pow2[N]
    ans = (numer * pow(denom, MOD - 2, MOD)) % MOD
    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque

read = sys.stdin.buffer.read


def main():
    MOD = 1000000007
    N, *AB = map(int, read().split())
    G = [[] for _ in range(N)]
    for a, b in zip(AB[::2], AB[1::2]):
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)

    stack = deque([0])
    order = []
    prev = [0] * N
    prev[0] = -1
    while stack:
        v = stack.pop()
        order.append(v)
        for nv in G[v]:
            if nv != prev[v]:
                stack.append(nv)
                prev[nv] = v

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

    nodes = [1] * N
    numer = 0

    for v in reversed(order):
        if prev[v] != -1:
            nodes[prev[v]] += nodes[v]
        numer = (numer + pow2[N - 1] - 1 - (pow2[N - nodes[v]] - 1)) % MOD
        for nv in G[v]:
            if nv != prev[v]:
                numer = (numer - (pow2[nodes[nv]] - 1)) % MOD

    denom = pow2[N]
    ans = (numer * pow(denom, MOD - 2, MOD)) % MOD
    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque

read = sys.stdin.buffer.read


def main():
    MOD = 1000000007
    N, *AB = map(int, read().split())
    G = [[] for _ in range(N)]
    for a, b in zip(AB[::2], AB[1::2]):
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)

    stack = deque([0])
    order = []
    prev = [0] * N
    prev[0] = -1
    while stack:
        v = stack.pop()
        order.append(v)
        for nv in G[v]:
            if nv != prev[v]:
                stack.append(nv)
                prev[nv] = v

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

    nodes = [1] * N
    numer = 0

    for v in reversed(order):
        if prev[v] != -1:
            nodes[prev[v]] += nodes[v]
        numer = (numer + pow2[N - 1] - 1 - (pow2[N - nodes[v]] - 1)) % MOD
        for nv in G[v]:
            if nv != prev[v]:
                numer = (numer - (pow2[nodes[nv]] - 1)) % MOD

    denom = pow2[N]
    ans = (numer * pow(denom, MOD - 2, MOD)) % MOD
    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    MOD = 1000000007
    N, *AB = map(int, read().split())
    G = [[] for _ in range(N)]
    for a, b in zip(AB[::2], AB[1::2]):
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)

    stack = deque([0])
    order = []
    prev = [0] * N
    prev[0] = -1
    while stack:
        v = stack.pop()
        order.append(v)
        for nv in G[v]:
            if nv != prev[v]:
                stack.append(nv)
                prev[nv] = v

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

    nodes = [1] * N
    numer = 0

    for v in reversed(order):
        if prev[v] != -1:
            nodes[prev[v]] += nodes[v]
        numer = (numer + pow2[N - 1] - 1 - (pow2[N - nodes[v]] - 1)) % MOD
        for nv in G[v]:
            if nv != prev[v]:
                numer = (numer - (pow2[nodes[nv]] - 1)) % MOD

    denom = pow2[N]
    ans = (numer * pow(denom, MOD - 2, MOD)) % MOD
    print(ans)
    return


if __name__ == '__main__':
    main()