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)
n = int(input())
G = [[] for _ in range(n)]
mod = 10**9 + 7

for _ in range(n-1):
    a,b = map(int,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



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

Solution (Python):
import os
import sys
from collections import defaultdict

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)





children_counts = [defaultdict(int) for _ in range(N)]
hist = []
root = 0
stack = [(root, None)]
while stack:
    v, parent = stack.pop()
    hist.append((v, parent))
    for u in graph[v]:
        if u == parent:
            continue
        stack.append((u, v))
hist.reverse()
dfs = [0] * N
for v, parent in hist:
    ret = 0
    for u in graph[v]:
        if u == parent:
            continue
        cnt = dfs[u]
        children_counts[v][cnt] += 1
        ret += cnt
    ret += 1
    if v != root:
        children_counts[v][N - ret] += 1
    dfs[v] = ret


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


E = [0] * N
for v, counts in enumerate(children_counts):
    if len(graph[v]) == 1:
        
        E[v] = pow2[N]
        continue
    
    e = pow2[N - 1]
    
    for children, cnt in counts.items():
        
        
        curo = pow2[children] - 1
        e += (curo * cnt) % MOD
    
    
    E[v] = (e + 1) % MOD

E = [(pow2[N] - e) % MOD for e in E]
ans = div_mod(sum(E), pow2[N], MOD)
print(ans)

Solution (Python):
import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))

import sys
input = sys.stdin.readline


N = int(input())

d2 = [1]
inverse = [0, 1]
for _ in range(N):
    d2.append(2*d2[-1]%mod)
for i in range( 2,  10):
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )

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

v2i = [0 for _ in range(N+1)]
def itt(v, p):
    cn = 0
    ms = []
    for u in G[v]:
        if u == p:
            continue
        un = itt(u, v)
        ms.append(un)
        cn += un
    if p != None:
        ms.append(N-1-cn)
    v2i[v] = ms
    return cn+1
itt(1, None)
r = 0
for v in range(1, N+1):
    ff = v2i[v]
    for f in ff:
        r += d2[f] - 1 % mod
r = N*d2[N-1]-N-r
for _ in range(N):
    r = r*500000004 % mod
print(r)

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
def r(a):
    for i in range(1, 10001):
        if i and a * i % mod <= 10000:
            return str(a*i%mod) + "/" + str(i)
        if i and -a * i % mod <= 10000:
            return str(-(-a*i%mod)) + "/" + str(i)
    return a
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 
B = [1] * N 
for i in R[::-1]:
    s = inv2
    for j in X[i]:
        s = (s * A[j]) % mod
    A[i] = s

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

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

reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

mod = 10**9+7

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

cnt = [0]*n
def dfs(cur, prev):
    tmp = 1
    for to in G[cur]:
        if to != prev:
            tmp += dfs(to, cur)
    cnt[cur] = tmp
    return tmp

dfs(0, -1)

power = [0]*(n)
powe2_n = pow(2, n, mod)
powe2_n = pow(powe2_n, mod-2, mod)
power[n-1] = powe2_n
for i in reversed(range(n-1)):
    powe2_n *= 2
    powe2_n %= mod
    power[i] = powe2_n
ans = 0
from collections import deque
que = deque()
que.append((0, -1))

while que:
    cur, prev = que.pop()
    if len(G[cur]) == 1:
        if prev == -1:
            que.append((G[cur][0], cur))
        continue

    prob = 1
    prob -= power[n-2]

    for to in G[cur]:
        if to == prev:
            bubun_cnt = n-cnt[cur]
        else:
            que.append((to, cur))
            bubun_cnt = cnt[to]
        tmp = 1-power[bubun_cnt-1]
        tmp *= power[n-1-bubun_cnt-1]
        prob -= tmp
    prob %= mod
    ans += power[0]*prob
    ans %= mod

print(ans)

Solution (Python):
import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))

import sys
input = sys.stdin.readline


N = int(input())

d2 = [1]
inverse = [0, 1]
for _ in range(N):
    d2.append(2*d2[-1]%mod)
for i in range( 2,  10):
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )

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

v2i = [0 for _ in range(N+1)]
def itt(v, p):
    cn = 0
    ms = []
    for u in G[v]:
        if u == p:
            continue
        un = itt(u, v)
        ms.append(un)
        cn += un
    if p != None:
        ms.append(N-1-cn)
    v2i[v] = ms
    return cn+1
itt(1, None)
r = 0
for v in range(1, N+1):
    ff = v2i[v]
    for f in ff:
        r += d2[f] - 1 % mod
r = N*d2[N-1]-N-r
for _ in range(N):
    r = r*500000004 % mod
print(r)

Solution (Python):
from collections import deque

LARGE = 10 ** 9 + 7


def solve(n, a_list, b_list):
    
    g = [[] for _ in range(n)]
    for i in range(n - 1):
        a = a_list[i] - 1
        b = b_list[i] - 1
        g[a].append(b)
        g[b].append(a)

    parent = [-1] * n
    children = [[] for _ in range(n)]
    depth = [0] * n

    
    queue = deque([0])
    while len(queue) > 0:
        p = queue.popleft()
        for q in g[p]:
            if q == parent[p]:
                continue
            parent[q] = p
            children[p].append(q)
            depth[q] = depth[p] + 1
            queue.append(q)

    
    weight = [1] * n
    deeper = list(sorted([[i, depth[i]] for i in range(n)], key=lambda x: x[1], reverse=True))
    for i, _ in deeper:
        for j in children[i]:
            weight[i] += weight[j]

    
    res_array = [0] * n
    
    for i in range(1, n):
        for j in children[i]:
            res_array[n - 1 - weight[j]] += 1
        res_array[weight[i] - 1] += 1
        res_array[n - 1] -= len(children[i])
    for j in children[0]:
        res_array[n - 1 - weight[j]] += 1
    res_array[n - 1] -= len(children[0]) - 1
    

    res_a = pow(2, n - 1, LARGE) * n
    res_a %= LARGE
    
    for i in range(n):
        res_a -= pow(2, n - i - 1, LARGE) * res_array[i]
        res_a %= LARGE
        
    res_b = pow(2, n, LARGE)

    res = res_a * pow(res_b, LARGE - 2, LARGE) % LARGE
    
    return res


def main():
    n = int(input())
    a_list = [0] * (n - 1)
    b_list = [0] * (n - 1)
    for i in range(n - 1):
        a, b = map(int, input().split())
        a_list[i] = a
        b_list[i] = b
    res = solve(n, a_list, b_list)
    print(res)


def test():
    assert solve(3, [1, 2], [2, 3]) == 125000001
    assert solve(4, [1, 2, 3], [2, 3, 4]) == 375000003
    assert solve(4, [1, 1, 1], [2, 3, 4]) == 250000002


if __name__ == "__main__":
    test()
    main()

Solution (Python):
import sys 
sys.setrecursionlimit(10**9)
N = int(input())
G = [[] for _ in range(N)]
mod = 10**9+7
for _ in range(N-1):
    A, B = map(int, input().split())
    G[A-1].append(B-1)
    G[B-1].append(A-1)
cnt = [[] for _ in range(N)]
que = [0]
depth = [-1]*N
depth[0] = 0
while que:
    v = que.pop()
    d = depth[v]
    for nv in G[v]:
        if depth[nv]>=0:
            continue
        depth[nv] = d+1
        que.append(nv)
d_to_i = [[] for _ in range(N)]
for i in range(N):
    d_to_i[depth[i]].append(i)
for d in range(N)[::-1]:
    for v in d_to_i[d]:
        for nv in G[v]:
            if depth[nv]<depth[v]:
                continue
            if cnt[nv]:
                cnt[v].append(sum(cnt[nv])+1)
            else:
                cnt[v].append(1)
for i in range(N):
    res = N-1
    for j in cnt[i]:
        res-=j
    cnt[i].append(res)
ans = 0
p = [1]*N
for i in range(1, N):
    p[i] = p[i-1]*2%mod
for v in range(N):
    if len(cnt[v])<=1:
        continue    
    res = p[N-1]-1
    for a in cnt[v]:
        res-=p[a]-1
    ans+=res
    ans%=mod
inv = pow(2, (mod-2)*N, mod)
print(ans*inv%mod)

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

mod = 10**9+7
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)

st = [1]
seen = [0] * (N+1)
seen[1] = 1
child = [[] for _ in range(N+1)]
seq = []
while st:
    v = st.pop()
    seq.append(v)
    for u in adj[v]:
        if not seen[u]:
            seen[u] = 1
            st.append(u)
            child[v].append(u)
seq.reverse()

ans = 0
half = pow(2, mod-2, mod)
half_n = pow(half, N-1, mod)
dp = [1] * (N+1)
for v in seq:
    tmp = (1 - half_n)%mod
    tmp2 = 0
    for u in child[v]:
        dp[v] += dp[u]
        tmp2 = (tmp2 + ((1 - pow(half, dp[u], mod))%mod * pow(half, N-dp[u]-1, mod)) % mod) % mod
    if dp[v] < N:
        tmp2 = (tmp2 + ((1 - pow(half, N-dp[v], mod)) % mod * pow(half, dp[v]-1, mod)) % mod) % mod
    if child[v]:
        tmp = (tmp - tmp2) % mod
        ans = (ans + tmp) % mod

print((ans * half)%mod)

Solution (Python):
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

from collections import deque

mod = 10**9+7

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

que = deque()
dep = [0]*n
que.append((0,-1, 0))
order = []
while que:
    cur, prev, d = que.popleft()
    dep[cur] = d
    order.append(cur)
    for to in G[cur]:
        if to != prev:
            que.append((to, cur, d+1))

cnt = [1]*n
for i in reversed(order):
    for to in G[i]:
        if dep[to] < dep[i]:
            cnt[to] += cnt[i]

power = [0]*(n)
powe2_n = pow(2, n, mod)
powe2_n = pow(powe2_n, mod-2, mod)
power[n-1] = powe2_n
for i in reversed(range(n-1)):
    powe2_n *= 2
    powe2_n %= mod
    power[i] = powe2_n
ans = 0
que = deque()
que.append((0, -1))

while que:
    cur, prev = que.pop()
    if len(G[cur]) == 1:
        if prev == -1:
            que.append((G[cur][0], cur))
        continue

    prob = 1
    prob -= power[n-2]

    for to in G[cur]:
        if to == prev:
            bubun_cnt = n-cnt[cur]
        else:
            que.append((to, cur))
            bubun_cnt = cnt[to]
        tmp = 1-power[bubun_cnt-1]
        tmp *= power[n-1-bubun_cnt-1]
        prob -= tmp
    prob %= mod
    ans += power[0]*prob
    ans %= mod

print(ans)

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)
p_size = [N-1] * (N+1)
prod = [1] * (N+1)
coef = [1] * (N+1)
for v in order[::-1]:
    p = parent[v]
    x = size[v]
    size[p] += x
    prod[p] *= power_inv[x]; prod[p] %= MOD
    coef[p] += power[x] - 1
    x = N - x
    prod[v] *= power_inv[x]
    coef[v] += power[x] - 1
    E = 1 - prod[v] * coef[v] % MOD
    answer += E

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

Solution (Python):


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
 
n = int(input())

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



cnt = [-1]*n
parent = [-1]*n

q = [0]
order = []
while q:
    v = q.pop()
    order.append(v)
    for c in g[v]:
        if parent[v] != c:
            parent[c] = v
            q.append(c)

MOD = 10**9+7

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


num = [0]*n
ans = 0
for v in reversed(order):
    res = 1
    nokori = n-1
    for c in g[v]:
        if c != parent[v]:
            nc = num[c]+1
            res += pow2[nc] - 1
            num[v] += nc
            nokori -= nc
            
    res += pow2[nokori] - 1
    
    ans += pow2[n-1]-res 





R = (MOD+1)//2

print(ans*pow(R,n,MOD)%MOD)

Solution (Python):


import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
 
n = int(input())

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



cnt = [-1]*n
parent = [-1]*n

q = [0]
order = []
while q:
    v = q.pop()
    order.append(v)
    for c in g[v]:
        if parent[v] != c:
            parent[c] = v
            q.append(c)

MOD = 10**9+7

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


num = [0]*n
ans = 0
for v in reversed(order):
    res = 1
    nokori = n-1
    for c in g[v]:
        if c != parent[v]:
            nc = num[c]+1
            res += pow2[nc] - 1
            num[v] += nc
            nokori -= nc
            
    res += pow2[nokori] - 1
    
    ans += pow2[n-1]-res 





R = (MOD+1)//2

print(ans*pow(R,n,MOD)%MOD)

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