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



Sample input:
3
1 2
2 3


Sample output:
125000001

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

# (1/2)^n
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)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
 
n = int(input())
#n = [int(i) for i in readline().split()]
 
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)
 

#from collections import deque

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
            #print(c,v,nc)
    res += pow2[nokori] - 1
    #print(res,nokori)
    ans += pow2[n-1]-res 

#print(parent)
#print(num)
#print(pow2)

R = (MOD+1)//2

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

Submission status: Accepted

Solution code:
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)

# (1/2)^n
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)

Submission status: Runtime Error

Solution code:
# 75

from fractions import Fraction

MOD = 10**9+7
N = int(input())
g_l = [[] for i in range(N)]
check_l = [-1] * N
num_l = [0] * N
for i in range(N-1):
    ai, bi = map(int, input().split())
    g_l[ai-1].append(bi-1)
    g_l[bi-1].append(ai-1)


def dfs(n):
    d = 1
    if check_l[n] > 0:
        return num_l[n]
    check_l[n] = 1
    for next_n in g_l[n]:
        d += dfs(next_n)
    num_l[n] = d
    return d


def modpow(a, n):
    # calc : (a**n)%MOD
    ret = 1
    while n > 0:
        if n & 1:
            ret = (ret * a) % MOD
        a = (a * a) % MOD
        n >>= 1
    return ret


def modinv(a):
    # calc : (a**(-1)) %MOD
    return modpow(a, MOD-2)


dfs(0)

ans = 0
for i in range(1, N):
    ans += (1 - (1/2)**num_l[i]) * (1 - (1/2)**(N-num_l[i]))
ans += 1 - (1/2)**N  # 辺の期待値→頂点の期待値に変換(空集合以外は+1される)
ans -= N/2  # 黒点の期待値を引く

tmp = Fraction(ans)
x = tmp.denominator
y = tmp.numerator

z = (modinv(x) * y) % MOD

print(z)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
edges = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    edges[a - 1].append((b - 1, i))
    edges[b - 1].append((a - 1, i))
l = [0 for i in range(n)]
def dfs(cur, x):
    res = 1
    for i in edges[cur]:
        if i[1] != x:
            res += dfs(i[0], i[1])
    l[x] = res
    return res
dfs(0, -1)
l2 = [1]
i2 = pow(2, mod - 2, mod)
for i in range(n):
    l2.append(l2[-1] * i2 % mod)
cnt = 0
for i in l:
    cnt += (1 - l2[i]) * (1 - l2[n - i])
print((-n * i2 - l2[-1] + cnt + 1) % mod)

Submission status: Runtime Error

Solution code:
mod = 10 ** 9 + 7
n = int(input())
edges = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    edges[a - 1].append((b - 1, i))
    edges[b - 1].append((a - 1, i))
l = [0 for i in range(n)]
def dfs(cur, x):
    res = 1
    for i in edges[cur]:
        if i[1] != x:
            res += dfs(i[0], i[1])
    l[x] = res
    return res
dfs(0, -1)
l2 = [1]
i2 = pow(2, mod - 2, mod)
for i in range(n):
    l2.append(l2[-1] * i2 % mod)
cnt = 0
for i in l:
    cnt += (1 - l2[i]) * (1 - l2[n - i])
print((-n * i2 - l2[-1] + cnt + 1) % mod)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline


def calc_counts(n, edges):
    counts = [0] * n
    seen = [False] * n
    dfs(0, edges, seen, counts)
    return counts


def dfs(node, edges, seen, counts):
    count = 1
    seen[node] = True
    for to in edges[node]:
        if seen[to]:
            continue
        count += dfs(to, edges, seen, counts)
    counts[node] = count
    return count


def calc_blank(node, counts: list, edges, all, mod=10**9+7):
    n = len(counts)
    paths = edges[node]
    if len(paths) <= 1:
        return 0
    base = counts[node]
    result = all - 1
    for v in paths:
        count = counts[v]
        if count > base:
            count = n - base
        result -= pow(2, count, mod) - 1
        result %= mod

    return result


def main():
    mod = 10**9 + 7
    n = int(input())
    edges = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(int, input().split())
        edges[a-1].append(b-1)
        edges[b-1].append(a-1)

    counts = calc_counts(n, edges)
    all = pow(2, n-1, mod)
    blanks = 0
    for node in range(n):
        blank = calc_blank(node, counts, edges, all)
        blanks += blank
        blanks %= mod

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


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from collections import deque

class Node:
    def __init__(self):
        self.size = 1  # 自分以下のノードの数
        self.children = []

def dfs(v):
    V = Node()
    visited[v] = True
    for u in AL[v]:
        if visited[u]: continue
        U = dfs(u)
        V.size += U.size
        V.children.append(U)
    return V

def anaaki(V):
    ret = pow(2, n - 1, p) - 1
    for ch in V.children:
        ret -= pow(2, ch.size) - 1
        ret %= p
    ret -= pow(2, n - V.size) - 1
    ret %= p
    return ret

n = int(input())
AL = [[] for _ in range(n)]
visited = [False] * n
p = 10 ** 9 + 7
for i in range(n - 1):
    a, b = [int(x) - 1 for x in input().split()]
    AL[a].append(b)
    AL[b].append(a)

# dfs
root = dfs(0)
que = deque([root])
numer = 0
while que:
    next = que.popleft()
    numer += anaaki(next)
    numer %= p
    for ch in next.children:
        que.append(ch)

denom = pow(2, n, p)

print( numer * pow(denom, p - 2, p) % p)

Submission status: Runtime Error

Solution code:
mod = 10**9+7
p2 = [1]*(3*10**5)
for n in range(3*10**5-1):
    p2[n+1] = p2[n]*2%mod

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

l1 = [0]*(N+1)
l2 = [[] for _ in range(N+1)]

def rec(p,c):
    res = 0
    for a in g[c]:
        if a == p:
            continue
        n = rec(c,a)
        l2[c].append(n+1)
        res += n+1
    l1[c] = res
    return res

n = rec(0,1)
for i in range(1,N+1):
    l2[i].append(N-1-l1[i])

ans = 0
for i in range(1,N+1):
    ans += p2[N-1]-1
    ans %= mod
    for j in l2[i]:
        ans -= p2[j]-1
        ans %= mod
ans *= pow(p2[N],mod-2,mod)
ans %= mod
print(ans)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline

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

ans = 0
size = [1] * N

def dfs(v, p):
    for c in G[v]:
        if c == p:
            continue
        dfs(c, v)
        size[v] += size[c]

dfs(0, -1)

def dfs2(v, p):
    global ans
    prob1 = 0
    s = 1
    for c in G[v]:
        if c == p:
            continue
        s += size[c]
        prob1 += (1 - pow(2, size[c] * (mod - 2), mod)) * pow(2, (N - size[c]) * (mod - 2), mod) % mod
        prob1 %= mod
        dfs2(c, v)
    prob1 += (1 - pow(2, (N - s) * (mod - 2), mod)) * pow(2, s * (mod - 2), mod) % mod
    prob1 %= mod
    prob = pow(2, mod - 2, mod) - pow(2, N * (mod - 2), mod) - prob1
    prob %= mod
    ans = (ans + prob) % mod

dfs2(0, -1)
print(ans)

Submission status: Runtime Error

Solution code:
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()

Submission status: Runtime Error

Solution code:
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)
#print(tree)

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)
#print(tree_dic)

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
#print(bunshi,bumbo)

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

Submission status: Runtime Error

Solution code:
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)

  # print(v, ts)

  now = pow(2, N-1, MOD)-1
  for t in ts:
    now -= pow(2, t, MOD)-1
  ans += now
  return res

ans = 0
MOD = 10**9+7
dfs(1)
print((ans * pow(pow(2, N, MOD), MOD-2, MOD)) % MOD)

Submission status: Runtime Error

Solution code:
# Surrounded Nodes
from collections import deque
import sys
sys.setrecursionlimit(10**7)
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)


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:
        c = 2**(N-1)
        for x in G[i]:
            if x != parent[i]:
                c -= 2**count[x]
        c -= 2**(N-count[i])
        c += len(G[i])-1
        ans += c
D = pow(2, N, mod)
print(c*pow(D, mod-2, mod) % mod)

Submission status: Runtime Error

Solution code:
# Surrounded Nodes
from collections import deque
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)


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:
        c = 2**(N-1)
        for x in G[i]:
            if x != parent[i]:
                c -= 2**count[x]
        c -= 2**(N-count[i])
        c += len(G[i])-1
        ans += c
D = pow(2, N, mod)
print(ans*pow(D, mod-2, mod) % mod)

Submission status: Runtime Error

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


### 木の読み込み tree

# サイズが大きいとdefaultdictが早い(for文を書かなくて済む)
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)

bs = {}
def sub(u, p):
    if (p,u) in bs:
        return bs[p,u]
    b = 1
    ps = []
    for v in ns[u]:
        if v==p:
            continue
        bb = sub(v, u)
        b += bb
    bs[p,u] = b
    return b

def sub2(u, p):
    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
        sub2(v,u)
        
sub(0, -1)
bs[0,-1] = 0
sub2(0,-1)
# ans[0] = bs[-1,0]
raise RuntimeError
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)

Submission status: Runtime Error

Solution code:
#解説方針#解法1
from collections import deque
from heapq import heappop, heappush
#標準入力
N = int(input())
mod = 10 ** 9 + 7
L = [[] for i in range(N + 1)] #dfs用
AB = [0] * (N - 1)
for i in range(N - 1):
  a, b = map(int, input().split())
  L[a].append(b)
  L[b].append(a)
  AB[i] = [a, b]
#print(L)
#逆元計算
#P = 10 ** 9 + 7
#N2 = 2 * 100000 + 1
#inv_t = [0]+[1]
#for i in range(2,N2):
#  inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

#各辺がSに含まれる確率を求める
def dfs(c, d):#辺をつなぐ2頂点を変数にとる
  q = [c]
  visited = [0] * (N + 1)
  visited[c] = 1
  visited[d] = 1
  ans = 1
  while q:
    e = heappop(q)
    for i in L[e]:
      if visited[i] == 0:
        visited[i] = 1
        ans += 1
        heappush(q, i)
  #print(ans , N - ans)
  pro = (1-((1/2) ** ans)) * (1-((1/2) ** (N - ans)))
  return pro      

#頂点の個数の期待値にする。
#基本的に辺の数+1だが、黒の頂点が一つもない1パターン(確率 1 / 2**N)だけ別に考慮
x = 0
for i in range(N - 1):
  x += dfs(AB[i][0], AB[i][1])
x = x + 1 - (N / 2) - (1/2) ** N
#print(x)#期待値があっていることを確認
  
y = int(2 ** N * x)
z = 2 ** N
T = True
while T:
  if (y % 2 == 0) and (z % 2 == 0):
    y /= 2
    z /= 2
  else:
    T = False
    
#ここで x = y / (2 ** N)の形にする
y, z = y % mod, int(z % mod)
y = y % z
print(y, z)
#ans = inv_t[z] * 1
#print(int(ans))

Submission status: Runtime Error

Solution code:
#解説方針#解法1
from collections import deque
#標準入力
N = int(input())
mod = 10 ** 9 + 7
L = [[] for i in range(N + 1)] #dfs用
AB = [0] * (N - 1)
for i in range(N - 1):
  a, b = map(int, input().split())
  L[a].append(b)
  L[b].append(a)
  AB[i] = [a, b]
#print(L)
#逆元計算
P = 10 ** 9 + 7
N2 = 2 * 100000 + 1
inv_t = [0]+[1]
for i in range(2,N2):
  inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

#各辺がSに含まれる確率を求める
def dfs(c, d):#辺をつなぐ2頂点を変数にとる
  q = deque([c])
  visited = [0] * (N + 1)
  visited[c] = 1
  visited[d] = 1
  ans = 1
  while q:
    e = q.pop()
    for i in L[e]:
      if visited[i] == 0:
        visited[i] = 1
        ans += 1
        q.append(i)
  #print(ans , N - ans)
  pro = (1-((1/2) ** ans)) * (1-((1/2) ** (N - ans)))
  return pro      

#頂点の個数の期待値にする。
#基本的に辺の数+1だが、黒の頂点が一つもない1パターン(確率 1 / 2**N)だけ別に考慮
x = 0
for i in range(N - 1):
  x += dfs(AB[i][0], AB[i][1])
x = x + 1 - (N / 2) - (1/2) ** N
#print(x)#期待値があっていることを確認
  
y = int(2 ** N * x)
z = 2 ** N
T = True
while T:
  if (y % 2 == 0) and (z % 2 == 0):
    y /= 2
    z /= 2
  else:
    T = False
    
#ここで x = y / (2 ** N)の形にする
y, z = y % mod, int(z % mod)
y = y % z
#print(y, z)
ans = inv_t[z] * 1
print(int(ans))

Submission status: Runtime Error

Solution code:
#解説方針#解法1
from collections import deque
#標準入力
N = int(input())
mod = 10 ** 9 + 7
L = [[] for i in range(N + 1)] #dfs用
AB = [0] * (N - 1)
for i in range(N - 1):
  a, b = map(int, input().split())
  L[a].append(b)
  L[b].append(a)
  AB[i] = [a, b]
#print(L)
#逆元計算
P = 10 ** 9 + 7
N2 = 2 * 100000 + 1
inv_t = [0]+[1]
for i in range(2,N2):
  inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

#各辺がSに含まれる確率を求める
def dfs(c, d):#辺をつなぐ2頂点を変数にとる
  q = deque([c])
  visited = [0] * (N + 1)
  visited[c] = 1
  visited[d] = 1
  ans = 1
  while q:
    e = q.pop()
    for i in L[e]:
      if visited[i] == 0:
        visited[i] = 1
        ans += 1
        q.append(i)
  #print(ans , N - ans)
  pro = (1-((1/2) ** ans)) * (1-((1/2) ** (N - ans)))
  return pro      

#頂点の個数の期待値にする。
#基本的に辺の数+1だが、黒の頂点が一つもない1パターン(確率 1 / 2**N)だけ別に考慮
x = 0
for i in range(N - 1):
  x += dfs(AB[i][0], AB[i][1])
x = x + 1 - (N / 2) - (1/2) ** N
#print(x)#期待値があっていることを確認
  
y = int(2 ** N * x)
z = 2 ** N
T = True
while T:
  if (y % 2 == 0) and (z % 2 == 0):
    y /= 2
    z /= 2
  else:
    T = False
    
#ここで x = y / (2 ** N)の形にする
y, z = y % mod, int(z % mod)
y = y % z
print(y, z)
ans = inv_t[z] * 1
print(int(ans))

Submission status: Runtime Error

Solution code:
import heapq
import copy
  
N = int(input())
ab = [[] * (N + 1) for i in range(N + 1)]
E = [0] * (N - 1)
for i in range(N - 1):
  a, b = map(int, input().split())
  ab[a].append(b)
  ab[b].append(a)
  E[i] = [a, b]
#print(ab)

#xとyを根とする部分木の頂点の数を求める
size = [1] * (N + 1)
def dfs_depandsize(tree,v,p):
    for x in tree[v]:
        if x == p:
            continue
        size[v] += dfs_depandsize(tree,x,v)
    return size[v]
dfs_depandsize(ab, 1, -1)
#print(size)

#print(dfs(2, 3))
#(1 - (1/ 2) ** c) * (1 - (1/ 2) ** (N - c)) + 1
#上式を辺ごとに全て足し合わせたものがSの頂点の個数の期待値
#そこからN / 2を引けば求める期待値
#逆元を考える必要があるため、分母と分子に分けて考える

t = 2 ** N#分母
s = 0#分子
for i in range(N - 1):
  c = min(size[E[i][0]], size[E[i][1]])
  #print(c)
  s += (2 ** N + 1 - 2 ** (N - c) - 2 ** c) 
  
#辺の個数を数えたので、それに2 ** Nを足して、頂点の個数にする
#-1は空グラフをケア
s += 2 ** N - 1  
s -= N * 2 ** (N - 1)

#逆元計算
p = 10 ** 9 + 7
t_inv = pow(t, p-2, p)
ans = t_inv * s % p
print(ans)

Submission status: Runtime Error

Solution code:
import heapq
import copy
  
N = int(input())
ab = [[] * (N + 1) for i in range(N + 1)]
E = [0] * (N - 1)
for i in range(N - 1):
  a, b = map(int, input().split())
  ab[a].append(b)
  ab[b].append(a)
  E[i] = [a, b]
#print(ab)

#xとyを根とする部分木の頂点の数を求める
size = [1] * (N + 1)
def dfs_depandsize(tree,v,p):
    for x in tree[v]:
        if x == p:
            continue
        size[v] += dfs_depandsize(tree,x,v)
    return size[v]
dfs_depandsize(ab, 1, -1)
print(size)

#print(dfs(2, 3))
#(1 - (1/ 2) ** c) * (1 - (1/ 2) ** (N - c)) + 1
#上式を辺ごとに全て足し合わせたものがSの頂点の個数の期待値
#そこからN / 2を引けば求める期待値
#逆元を考える必要があるため、分母と分子に分けて考える

t = 2 ** N#分母
s = 0#分子
for i in range(N - 1):
  c = min(size[E[i][0]], size[E[i][1]])
  #print(c)
  s += (2 ** N + 1 - 2 ** (N - c) - 2 ** c) 
  
#辺の個数を数えたので、それに2 ** Nを足して、頂点の個数にする
#-1は空グラフをケア
s += 2 ** N - 1  
s -= N * 2 ** (N - 1)

#逆元計算
p = 10 ** 9 + 7
t_inv = pow(t, p-2, p)
ans = t_inv * s % p
print(ans)

Submission status: Runtime Error

Solution code:
import heapq
import copy
  
N = int(input())
ab = [[] * (N + 1) for i in range(N + 1)]
E = [0] * (N - 1)
for i in range(N - 1):
  a, b = map(int, input().split())
  ab[a].append(b)
  ab[b].append(a)
  E[i] = [a, b]
#print(ab)

#xとyを根とする部分木の頂点の数を求める
size = [1] * (N + 1)
def dfs_depandsize(tree,v,p):
    for x in tree[v]:
        if x == p:
            continue
        size[v] += dfs_depandsize(tree,x,v)
    return size[v]
dfs_depandsize(ab, 1, 0)
print(size)

#print(dfs(2, 3))
#(1 - (1/ 2) ** c) * (1 - (1/ 2) ** (N - c)) + 1
#上式を辺ごとに全て足し合わせたものがSの頂点の個数の期待値
#そこからN / 2を引けば求める期待値
#逆元を考える必要があるため、分母と分子に分けて考える

t = 2 ** N#分母
s = 0#分子
for i in range(N - 1):
  c = min(size[E[i][0]], size[E[i][1]])
  #print(c)
  s += (2 ** N + 1 - 2 ** (N - c) - 2 ** c) 
  
#辺の個数を数えたので、それに2 ** Nを足して、頂点の個数にする
#-1は空グラフをケア
s += 2 ** N - 1  
s -= N * 2 ** (N - 1)

#逆元計算
p = 10 ** 9 + 7
t_inv = pow(t, p-2, p)
ans = t_inv * s % p
print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
AB = []
query = [[] for _ in range(N)]
mod = 10**9+7
for _ in range(N-1):
    a, b = map(int, input().split())
    query[a-1].append(b-1)
    query[b-1].append(a-1)
    AB.append((a-1, b-1))

edges = [0]*N
def dfs(b, v):
    lis = []
    cum = 0
    for i in query[v]:
        if i==b:
            continue
        cum += dfs(v, i)
    if cum==0:
        return 1
    edges[v] = cum
    return cum+1

dfs(0, 0)
ans = 0
for a, b, in AB:
    x = min(edges[a], edges[b])+1
    ans += (1-pow(pow(2, x, mod), mod-2, mod))*(1-pow(pow(2, N-x, mod), mod-2, mod))
    ans %= mod
ans = ans - N*pow(2, mod-2, mod)+1-pow(pow(2, N, mod), mod-2, mod)
print(ans%mod)

Submission status: Runtime Error

Solution code:
N = int(input())
AB = []
query = [[] for _ in range(N)]
mod = 10**9+7
for _ in range(N-1):
    a, b = map(int, input().split())
    query[a-1].append(b-1)
    query[b-1].append(a-1)
    AB.append((a-1, b-1))

edges = [0]*N
def dfs(b, v):
    lis = []
    for i in query[v]:
        if i==b:
            continue
        lis.append(dfs(v, i))
    if len(lis)==0:
        return 1
    edges[v] = sum(lis)
    return sum(lis)+1

dfs(0, 0)
ans = 0
for a, b, in AB:
    x = min(edges[a], edges[b])+1
    ans += (1-pow(pow(2, x, mod), mod-2, mod))*(1-pow(pow(2, N-x, mod), mod-2, mod))
    ans %= mod
ans = ans - N*pow(2, mod-2, mod)+1-pow(pow(2, N, mod), mod-2, mod)
print(ans%mod)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)

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

cs = [1] * N
def dfs(v,p=-1):
    ret = 1
    for to in es[v]:
        if to==p: continue
        ret += dfs(to,v)
    cs[v] = ret
    return ret
dfs(0)
ans = 0
for i in range(N):
    if len(es[i]) == 1: continue
    ans += pow(2,N-1,MOD) - 1
    c = 0
    for to in es[i]:
        if cs[to] > cs[i]: continue
        c += cs[to]
        ans -= pow(2,cs[to],MOD) - 1
    ans -= pow(2,N-c-1,MOD) - 1

ans *= pow(2,-N,MOD)
print(ans%MOD)