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: Time Limit Exceeded

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

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)

# 頂点1をルートにして各頂点より下にある部分木の頂点数を求めていく
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)

# 2の累乗を事前に計算しておく
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)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:

"""
Writer: SPD_9X2
https://atcoder.jp/contests/abc149/tasks/abc149_f

全方位木dpか？
→保持する値は、小部分木の頂点の数

頂点数a,b,c,dの4つの部分木が付いてる時の確率は

1/2 * (1-黒を持つ成分が1つ以下の確率)

黒を持つ成分が1つ以下の確率 = all白の確率+aのみall白+bのみall白+c+d
all白の確率 = aが白*b*c*d = 1/2**(n-1)
aのみ黒 = (1-a)*b*c*d

aが白の確率 = (1/2) ** a

all白の確率は, 累計O(N)で構築可能
aのみ白・・etc は、あらかじめ(1-a)*(1-b)…を計算しておき、差分計算する
そうすれば全体O(N)で構築可能
結果としてO(N)で解ける。

全方位木dpでは、結局接続する小部分木の頂点の数の集合が分ければ解ける
→親部分木の大きさは分かるので全方位感がないね？

"""
import sys
sys.setrecursionlimit(500000)

def inverse(a,mod): #aのmodを法にした逆元を返す
    return pow(a,mod-2,mod)

N = int(input())

lis = [ [] for i in range(N) ]

for i in range(N-1):

    A,B = map(int,input().split())

    A -= 1
    B -= 1

    lis[A].append(B)
    lis[B].append(A)

mod = 10**9+7
half = 500000004
hxx = [1,half] #1/2の累乗をO(1)で出すための奴
bxx = [1,2] #2の累乗をO(1)で出す
for i in range(N):
    hxx.append(hxx[-1] * half % mod)
    bxx.append(bxx[-1] * 2 % mod)

ans = [0]

def dfs(v,p,ans):

    vns = []
    ret = 1

    for nex in lis[v]:

        if nex != p:
            cvn = dfs(nex,v,ans)
            ret += cvn
            vns.append(cvn)

    if N-1-sum(vns) != 0:
        vns.append(N-1-sum(vns))

    #答えを求めるパート
        
    b_zero_one = hxx[N-1]

    for i in vns:
        b_zero_one += hxx[N-1-i] * (1-hxx[i])

    #print (v,half * (1-b_zero_one) % mod)
    ans[0] += half * (1-b_zero_one)
    ans[0] %= mod

    return ret

ans = [0]
dfs(0,0,ans)
print (ans[0])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]

sys.setrecursionlimit(10**6)
MOD = 10**9+7

n = int(input())

pows = [1]
for _ in range(n):
	pows.append((pows[-1] * 500000004) % MOD)

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

ans = 0
def dfs(x, p):
	global ans
	cnt = 1
	tmp = 1 - pows[n-1]
	for v in adj[x]:
		if v == p:
			continue
		w = dfs(v, x)
		tmp -= pows[n-1-w] - pows[n-1]
		cnt += w
	if n > cnt:
		tmp -= pows[cnt-1] - pows[n-1]
	tmp *= 500000004
	ans = (ans + tmp) % MOD

	return cnt

dfs(0, -1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]

sys.setrecursionlimit(10**6)
MOD = 10**9+7

n = int(input())

pows = [1]
for _ in range(n):
	pows.append((pows[-1] * 500000004) % MOD)

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

ans = 0
def dfs(x, p):
	global ans
	cnt = 1
	tmp = 1 - pows[n-1]
	for v in adj[x]:
		if v == p:
			continue
		w = dfs(v, x)
		tmp -= pows[n-1-w] - pows[n-1]
		cnt += w
	if n > cnt:
		tmp -= pows[cnt-1] - pows[n-1]
	tmp = (tmp * 500000004) % MOD
	ans = (ans + tmp) % MOD

	return cnt

dfs(0, -1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!usr/bin/env python3
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():
    def dfs(x):
        res = 1
        for y in v[x]:
            if d[y]:
                d[y] = 0
                res += dfs(y)
        t[x] = res
        return res

    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)
    t = [0]*n
    d = [1]*n
    d[0] = 0
    dfs(0)
    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

#Solve
if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
mod = 10**9 + 7

def factorial(N,MOD,r=True):
    fact = [1]*(N+1)
    rfact = [1]*(N+1)
    r = 1
    for i in range(1,N+1):
        fact[i] = r = r * i % MOD
    rfact[N] = r = pow(fact[N],MOD-2,MOD)
    for i in range(N, 0, -1):
        rfact[i-1] = r = r * i % MOD
    if r:
        return fact,rfact
    else:
        return fact
fact,rfact = factorial(2*10**5,mod)
def perm(n,k): #上のfactorialと併用
    return fact[n]*rfact[n-k]%mod
def comb(n,k): #上のfactorialと併用
    return fact[n]*rfact[k]*rfact[n-k]%mod

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

euler = []
def dfs(pre,now):
    euler.append(now)
    for to in G[now]:
        if to == pre:
            continue
        dfs(now,to)
    euler.append(pre)

dfs(-1,0)

data = [[] for i in range(n)]
last = [-1]*n
for i,x in enumerate(euler[:-1]):
    if last[x] == -1:
        last[x] = i
        continue
    data[x].append((i-last[x])//2)
    last[x] = i

for i in range(n):
    if sum(data[i]) == n-1:
        continue
    data[i].append(n-1-sum(data[i]))

two = [1]
now = 1
for i in range(n):
    now *= 2
    now %= mod
    two.append(now)

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


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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
mod = 10**9 + 7

def factorial(N,MOD,r=True):
    fact = [1]*(N+1)
    rfact = [1]*(N+1)
    r = 1
    for i in range(1,N+1):
        fact[i] = r = r * i % MOD
    rfact[N] = r = pow(fact[N],MOD-2,MOD)
    for i in range(N, 0, -1):
        rfact[i-1] = r = r * i % MOD
    if r:
        return fact,rfact
    else:
        return fact
fact,rfact = factorial(2*10**5,mod)
def perm(n,k): #上のfactorialと併用
    return fact[n]*rfact[n-k]%mod
def comb(n,k): #上のfactorialと併用
    return fact[n]*rfact[k]*rfact[n-k]%mod

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

euler = []
def dfs(pre,now):
    euler.append(now)
    for to in G[now]:
        if to == pre:
            continue
        dfs(now,to)
    euler.append(pre)

dfs(-1,0)

data = [[] for i in range(n)]
last = [-1]*n
for i,x in enumerate(euler[:-1]):
    if last[x] == -1:
        last[x] = i
        continue
    data[x].append((i-last[x])//2)
    last[x] = i

for i in range(n):
    if sum(data[i]) == n-1:
        continue
    data[i].append(n-1-sum(data[i]))

two = [1]
now = 1
for i in range(n):
    now *= 2
    now %= mod
    two.append(now)

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


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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
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=float("inf")
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)

Submission status: Time Limit Exceeded

Solution code:
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=float("inf")
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=(cur-H[n-1-a])%mod
    ans=(ans+cur)%mod
print((ans*H[1])%mod)