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:
from sys import stdin
f_i = stdin

N = int(f_i.readline())

adj = [[] for i in range(N)]
for i in range(N - 1):
    A, B = map(int, f_i.readline().split())
    A -= 1
    B -= 1
    adj[A].append(B)
    adj[B].append(A)

mod = 10 ** 9 + 7
pow2 = [(2 ** i) % mod for i in range(N + 1)]

from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

ans = 0
def dfs(node, parent):
    global ans
    cnt = 1
    for child in adj[node]:
        if child != parent:
            cnt += dfs(child, node)
    
    ans += (pow2[cnt] - 1) * (pow2[N-cnt] - 1)
    return cnt

dfs(0, None)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
f_i = stdin

N = int(f_i.readline())

adj = [[] for i in range(N)]
for i in range(N - 1):
    A, B = map(int, f_i.readline().split())
    A -= 1
    B -= 1
    adj[A].append(B)
    adj[B].append(A)

from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

subtree_size = []
def dfs(node, parent):
    cnt = 1
    for child in adj[node]:
        if child != parent:
            cnt += dfs(child, node)
    
    subtree_size.append(cnt)
    return cnt

dfs(0, None)

mod = 10 ** 9 + 7
pow2 = [(2 ** i) % mod for i in range(N + 1)]

ans = 0
for s in subtree_size:
    ans += (pow2[s] - 1) * (pow2[N-s] - 1)

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
f_i = stdin

N = int(f_i.readline())

adj = [[] for i in range(N)]
for i in range(N - 1):
    A, B = map(int, f_i.readline().split())
    A -= 1
    B -= 1
    adj[A].append(B)
    adj[B].append(A)

from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

subtree_size = []
def dfs(node, parent):
    cnt = 1
    for child in adj[node]:
        if child != parent:
            cnt += dfs(child, node)
    
    if cnt != N:
        subtree_size.append(cnt)
    return cnt

dfs(0, None)

mod = 10 ** 9 + 7
pow2 = [(2 ** i) % mod for i in range(N + 1)]

ans = 0
for s in subtree_size:
    ans += (pow2[s] - 1) * (pow2[N-s] - 1)

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

print(ans)

Submission status: Time Limit Exceeded

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

mod = 10 ** 9 + 7

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

sub_size = [[] for _ in range(N)]

def dfs(cur=0, pre=-1) :
  s = 0
  for nex in vec[cur] :
    if nex == pre :
      continue
    t = dfs(nex, cur)
    s += t
    sub_size[cur].append(t)
  if s != N - 1 :
    sub_size[cur].append(N - 1 - s)

  return s + 1

dfs()

power = [1]
for _ in range(N) :
  power.append(power[-1]*2%mod)

ret = 0
for i in range(N) :
  tmp = power[N-1]-1
  for ss in sub_size[i] :
    tmp -= power[ss]-1
  ret += tmp

ret = ret*pow(power[N], mod - 2, mod)% mod

print(ret)

Submission status: Time Limit Exceeded

Solution code:
from sys import setrecursionlimit
setrecursionlimit(200200)
MOD=10**9+7
N = int(input())
AB = [tuple(map(int, input().split())) for _ in range(N-1)]
G = [[] for _ in range(N)]
for i, (a, b) in enumerate(AB):
    a -= 1
    b -= 1
    G[a].append((b, i))
    G[b].append((a, i))

P = [0] * N
visited = [False] * N
visited[0] = True
def dfs(x, i):
    e = 1
    for v, c in G[x]:
        if not visited[v]:
            visited[v] = True
            e += dfs(v, c)
    P[i] = e
    return e

dfs(0, -1)
W = [1] * (N + 1)
inv_2 = pow(2, MOD-2, MOD)
for i in range(N):
    W[i+1] = W[i]*inv_2%MOD
ans = (W[N] + 1) * (N - 1) % MOD
for i in range(N-1):
    ans -= W[P[i]] + W[N-P[i]]
    ans %= MOD
print((ans - inv_2*N - W[N] + 1) % MOD)

Submission status: Time Limit Exceeded

Solution code:
MOD=10**9+7
class Fp(int):
    def __new__(self,x=0):return super().__new__(self,x%MOD)
    def inv(self):return self.__class__(super().__pow__(MOD-2,MOD))
    def __add__(self,value):return self.__class__(super().__add__(value))
    def __sub__(self,value):return self.__class__(super().__sub__(value))
    def __mul__(self,value):return self.__class__(super().__mul__(value))
    def __floordiv__(self,value):return self.__class__(self*self.__class__(value).inv())
    def __pow__(self,value):return self.__class__(super().__pow__(value%(MOD-1), MOD))
    __radd__=__add__
    __rmul__=__mul__
    def __rsub__(self,value):return self.__class__(-super().__sub__(value))
    def __rfloordiv__(self,value):return self.__class__(self.inv()*value)
    def __iadd__(self,value):self=self+value;return self
    def __isub__(self,value):self=self-value;return self
    def __imul__(self,value):self=self*value;return self
    def __ifloordiv__(self,value):self=self//value;return self
    def __ipow__(self,value):self=self**value;return self
    def __neg__(self):return self.__class__(super().__neg__())

from sys import setrecursionlimit
setrecursionlimit(200200)
N = int(input())
AB = [tuple(map(int, input().split())) for _ in range(N-1)]
G = [[] for _ in range(N)]
for i, (a, b) in enumerate(AB):
    a -= 1
    b -= 1
    G[a].append((b, i))
    G[b].append((a, i))

P = [0] * N
visited = [False] * N
visited[0] = True
def dfs(x, i):
    e = 1
    for v, c in G[x]:
        if not visited[v]:
            visited[v] = True
            e += dfs(v, c)
    P[i] = e
    return e

dfs(0, -1)
ans = Fp(0)
one = Fp(1)
two = Fp(2)
for i in range(N-1):
    ans += (one-one//two**P[i])*(one-one//two**(N-P[i]))
print(ans-Fp(N)//2-two**-N+1)

Submission status: Time Limit Exceeded

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

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

def dfs(v, pv):
    global ans
    
    if memo[v]!=-1:
        return memo[v]
        
    add = pow(2, N-1, MOD)-1
    res = 1
    
    for nv in adj_list[v]:
        if nv==pv:
            continue
        
        add -= pow(2, dfs(nv, v), MOD)-1
        res += dfs(nv, v)
    
    add -= pow(2, N-res, MOD)-1
    ans += add
    ans %= MOD
    
    memo[v] = res
    
    return res
        
N = int(input())
adj_list = [[] for _ in range(N)]

for _ in range(N-1):
    Ai, Bi = map(int, input().split())
    adj_list[Ai-1].append(Bi-1)
    adj_list[Bi-1].append(Ai-1)

ans = 0
MOD = 10**9+7
memo = [-1]*N
dfs(0, -1)
ans *= inv(pow(2, N, MOD))
ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

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

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

def dfs(v, pv):
    global ans
    
    if memo[v]!=-1:
        return memo[v]
        
    add = pow(2, N-1, MOD)-1
    res = 1
    
    for nv in adj_list[v]:
        if nv==pv:
            continue
        
        add -= pow(2, dfs(nv, v), MOD)-1
        res += dfs(nv, v)
    
    add -= pow(2, N-res, MOD)-1
    ans += add
    ans %= MOD
    
    memo[v] = res
    
    return res
        
N = int(input())
adj_list = [[] for _ in range(N)]

for _ in range(N-1):
    Ai, Bi = map(int, input().split())
    adj_list[Ai-1].append(Bi-1)
    adj_list[Bi-1].append(Ai-1)

ans = 0
MOD = 10**9+7
memo = [-1]*N
dfs(0, -1)
ans *= inv(pow(2, N, MOD))
ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

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

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

def dfs(v, pv):
    global ans
    
    if memo[v]!=-1:
        return memo[v]
        
    add = pow(2, N-1, MOD)-1
    res = 1
    
    for nv in adj_list[v]:
        if nv==pv:
            continue
        
        add -= pow(2, dfs(nv, v), MOD)-1
        res += dfs(nv, v)
    
    add -= pow(2, N-res, MOD)-1
    ans += add
    memo[v] = res
    
    return res
        
N = int(input())
adj_list = [[] for _ in range(N)]

for _ in range(N-1):
    Ai, Bi = map(int, input().split())
    adj_list[Ai-1].append(Bi-1)
    adj_list[Bi-1].append(Ai-1)

ans = 0
MOD = 10**9+7
memo = [-1]*N
dfs(0, -1)
ans *= inv(pow(2, N, MOD))
ans %= MOD

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
import random
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,d):
        d[x] = 0
        for y in v[x]:
            if d[y]:
                size[x] += dfs(y,d)
        return size[x]

    n = I()
    v = [[] for i in range(n)]
    size = [1]*n
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    d = [1]*n
    r = n>>1
    dfs(r,d)
    inv = pow(2,mod-2,mod)
    ans = (1-pow(inv,n,mod)-n*inv)%mod
    p = [pow(inv,i,mod) for i in range(n)]
    for i in range(n):
        if r == i:
            continue
        a = size[r]-size[i]
        b = n-a
        ans += (p[a]-1)*(p[b]-1)%mod
        ans %= mod
    print(ans)
    return

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

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
import random
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,d):
        d[x] = 0
        for y in v[x]:
            if d[y]:
                size[x] += dfs(y,d)
        return size[x]

    n = I()
    v = [[] for i in range(n)]
    size = [1]*n
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    d = [1]*n
    dfs(0,d)
    inv = pow(2,mod-2,mod)
    ans = (1-pow(inv,n,mod)-n*inv)%mod
    p = [pow(inv,i,mod) for i in range(n)]
    for i in range(1,n):
        a = size[0]-size[i]
        b = n-a
        ans += (p[a]-1)*(p[b]-1)%mod
        ans %= mod
    print(ans)
    return

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

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
import random
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,d):
        d[x] = 0
        for y in v[x]:
            if d[y]:
                size[x] += dfs(y,d)
        return size[x]

    n = I()
    v = [[] for i in range(n)]
    size = [1]*n
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    d = [1]*n
    dfs(0,d)
    inv = pow(2,mod-2,mod)
    ans = (1-pow(inv,n,mod)-n*inv)%mod
    p = [pow(inv,i,mod) for i in range(n)]
    for i in range(1,n):
        a = size[0]-size[i]
        b = n-a
        ans += (1-p[a])*(1-p[b])%mod
        ans %= mod
    print(ans)
    return

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

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
import random
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,d):
        d[x] = 0
        for y in v[x]:
            if d[y]:
                size[x] += dfs(y,d)
        return size[x]

    n = I()
    v = [[] for i in range(n)]
    size = [1]*n
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    d = [1]*n
    dfs(0,d)
    inv = pow(2,mod-2,mod)
    ans = (1-pow(inv,n,mod)-n*inv)%mod
    for i in range(1,n):
        a = size[0]-size[i]
        b = n-a
        ans += (1-pow(inv,a,mod))*(1-pow(inv,b,mod))%mod
        ans %= mod
    print(ans)
    return

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

Submission status: Time Limit Exceeded

Solution code:
class Tree:
  C, RL = {}, {}
  R, N, D, S, P = None, None, None, None, None
  SN = None
  def __init__(s, num):
    s.N = num
  def set(s, a, b):
    if a in s.C: s.C[a].append(b)
    else: s.C[a] = [b]
    if b in s.C: s.C[b].append(a)
    else: s.C[b] = [a]
  def makeRank(s, root):
    s.R = [0] * s.N #各ノードのランク
    s.R[root] = 1
    s.RL[1] = [root] #各ランクのノード
    s.S = [[] for _ in range(s.N)] #各ノードの子ノード
    s.P = [-1] * s.N #各ノードの親ノード
    F = [root]
    s.D = 2
    while F != []:
      Ft = []
      s.RL[s.D] = []
      for i in F:
        for j in s.C[i]:
          if s.R[j] == 0:
            s.R[j] = s.D
            Ft.append(j)
            s.RL[s.D].append(j)
            s.S[i].append(j)
            s.P[j] = i
      s.D += 1
      F = Ft
  def dfs(s, x): #最遠のノード,距離
    t = [-1] * s.N
    S = [x]
    ans = x
    ansn = 0
    t[x] = 0
    while S != []:
      k = S.pop()
      for i in s.C[k]:
        if t[i] == -1:
          t[i] = t[k] + 1
          S.append(i)
          if t[i] > ansn:
            ansn = t[i]
            ans = i
    return ans, ansn
  def getDi(s, x = 0): #直径
    a, _ = s.dfs(x)
    b, ans = s.dfs(a)
    return ans
  def getDeep(s, x): #xの子孫のうち一番深い深さ
    ans = 0
    if x in s.S:
      for i in s.S[x]:
        ans = max(ans, s.getDeep(i))
      return ans + 1
    else:
      return 0
  def getParent(s, x, n): #xのn世代前の親
    if n == 0:
      return x
    if s.P[x] == -1:
      return -n
    return s.getParent(s.P[x], n - 1)
  def countSon(s):
    s.SN = [0] * s.N
    for i in range(s.D - 1, 0, -1):
      for j in s.RL[i]:
        cnt = 1
        for k in s.S[j]:
          cnt += s.SN[k]
        s.SN[j] = cnt

class powmod():
  F = [1, 2]
  Fi = [1, 2]
  I = [0, 1]
  def __init__(self, num, mod):
    self.MOD = mod
    k = 2
    for i in range(2, num + 1):
      self.F.append((self.F[-1] * k) % mod)
      self.I.append(mod - self.I[mod % k] * (mod // k) % mod)
      self.Fi.append(self.Fi[-1] * self.I[k] % mod)

class Inv:
  def __init__(s, mod):
    s.MOD = mod
  def modpow(s, a, n):
    res = 1
    while n > 0:
      if n & 1:
        res = res * a % s.MOD
      a = a * a % s.MOD
      n >>= 1
    return res
  def invx(s, a):
    return s.modpow(a, s.MOD - 2)
  def invL(s, a, n):
    ia = s.invx(a)
    L = [1] * (n + 1)
    for i in range(1, n + 1):
      L[i] = L[i - 1] * ia % s.MOD
    return L


N = int(input())
AB = [list(map(int, input().split())) for _ in range(N - 1)]

T = Tree(N)
L = [0] * N
for a, b in AB:
  T.set(a - 1, b - 1)
  L[a - 1] += 1
  L[b - 1] += 1

for i in range(N):
  if L[i] == 1:
    root = i

T.makeRank(root)
T.countSon()

MOD = 10 ** 9 + 7
ans = 0


PM = powmod(N, MOD)
I = Inv(MOD)

ans = 0
for i in range(N):
  if i == root: continue
  if T.S[i] == []: continue
  L = []
  cnt = 0
  for j in T.S[i]:
    L.append(T.SN[j])
    cnt += T.SN[j]
  L.append(N - cnt - 1)

  t = PM.F[N - 1] - 1
  for j in L:
    t = t - PM.F[j] + 1
    if t < 0:
      t += MOD
  ans = (ans + t * I.invx(PM.F[N])) % MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())

E=[[] for i in range(N+1)]

for i in range(N-1):
    x,y=map(int,input().split())
    E[x].append(y)
    E[y].append(x)

mod=10**9+7

from collections import deque
Q=deque()

USE=[0]*(N+1)
Q.append(1)
H=[0]*(N+1)
H[1]=1
USE[1]=1

while Q:
    x=Q.pop()
    for to in E[x]:
        if USE[to]==0:
            USE[to]=1
            H[to]=H[x]+1
            Q.append(to)

EH=[(h,ind+1) for ind,h in enumerate(H[1:])]
EH.sort(reverse=True)

COME=[1]*(N+1)
USE=[0]*(N+1)

for h,ind in EH:
    USE[ind]=1
    for to in E[ind]:
        if USE[to]==0:
            COME[to]+=COME[ind]

ANS=0
for i in range(1,N+1):
    SCORE=[]
    for j in E[i]:
        if COME[j]<COME[i]:
            SCORE.append(COME[j])

    if sum(SCORE)<N-1:
        SCORE.append(N-sum(SCORE)-1)

    AV=1

    for s in SCORE:
        AV+=pow(2,s,mod)-1

    ANS+=pow(2,N-1,mod)-AV
    #print(SCORE,AV)

print((ANS*pow(pow(2,N,mod),mod-2,mod))%mod)

Submission status: Time Limit Exceeded

Solution code:
p = 1000000007
N = int(input())
T = [[] for _ in range(N)]
for _ in range(N - 1):
  (a, b) = (int(x) - 1 for x in input().split())
  T[a].append(b)
  T[b].append(a)
P = [-1] * N
P[0] = 0
Q = [0]
for i in range(N):
  q = Q[i]
  for adj in T[q]:
    if 0 <= P[adj]:
      continue
    P[adj] = q
    Q.append(adj)
ST = [[] for _ in range(N)]
for q in Q[N - 1:0:-1]:
  s = sum(ST[q]) + 1
  ST[P[q]].append(s)
  ST[q].append(N - s)
B = [pow(1 << i, p - 2, p) for i in range(N)]
H = [0] * N
ans = 0
for S in ST:
  ans += B[1] * ((1 - B[-1] - sum([(B[N - 1 - s] * (1 - B[s])) % p for s in S])) % p)
  ans %= p
print(ans)

Submission status: Time Limit Exceeded

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

mod = 10 ** 9 + 7

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

sub_size = [[] for _ in range(N)]

def dfs(cur, pre) :
  s = 0
  for nex in vec[cur] :
    if nex == pre :
      continue
    t = dfs(nex, cur)
    s += t
    sub_size[cur].append(t)
  if s != N - 1 :
    sub_size[cur].append(N - 1 - s)

  return s + 1

dfs(0, -1)

fac = [1]
inv = [1]
div = pow(2, mod - 2, mod)
for _ in range(N) :
  fac.append(fac[-1] * 2 % mod)
  inv.append(inv[-1] * div % mod)

ret = 0
for i in range(N) :
  if len(sub_size[i]) < 2 :
    continue

  a, b = 1, 1
  for ss in sub_size[i] :
    a *= inv[ss]
    b += fac[ss] - 1
    a %= mod
    b %= mod
  ret += (1 - a * b) % mod
  ret %= mod

ret = ret * div % mod

print(ret)

Submission status: Time Limit Exceeded

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

mod = 10 ** 9 + 7

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

sub_size = [[] for _ in range(N)]

def dfs(cur, pre) :
  s = 0
  for nex in vec[cur] :
    if nex == pre :
      continue
    t = dfs(nex, cur)
    s += t
    sub_size[cur].append(t)
  if s != N - 1 :
    sub_size[cur].append(N - 1 - s)

  return s + 1

dfs(0, -1)

fac = [1]
inv = [1]
for _ in range(N) :
  fac.append(fac[-1] * 2 % mod)
  inv.append(pow(fac[-1], mod - 2, mod))

ret = 0
for i in range(N) :
  if len(sub_size[i]) < 2 :
    continue
  
  a, b = 1, 1
  for ss in sub_size[i] :
    a *= inv[ss]
    b += fac[ss] - 1
    a %= mod
    b %= mod
  ret += (1 - a * b) % mod
  ret %= mod

ret = ret * inv[1] % mod

print(ret)

Submission status: Time Limit Exceeded

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

mod = 10 ** 9 + 7

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

sub_size = [[] for _ in range(N)]

def dfs(cur, pre) :
  s = 0
  for nex in vec[cur] :
    if nex == pre :
      continue
    t = dfs(nex, cur)
    s += t
    sub_size[cur].append(t)
  return s + 1

dfs(0, -1)

ret = 0
for i in range(N) :
  if sum(sub_size[i]) != N - 1 :
    sub_size[i].append(N - 1 - sum(sub_size[i]))
  
  if len(sub_size[i]) <= 1 :
    continue

fac = [1]
inv = [1]
for _ in range(N) :
  fac.append(fac[-1] * 2 % mod)
  inv.append(pow(fac[-1], mod - 2, mod))

for i in range(N) :
  a, b = 1, 1
  for ss in sub_size[i] :
    a *= inv[ss]
    b += fac[ss] - 1
    a %= mod
    b %= mod
  ret += (1 - a * b) % mod
  ret %= mod

ret = ret * inv[1] % mod

print(ret)

Submission status: Time Limit Exceeded

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

mod = 10 ** 9 + 7

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

sub_size = [[] for _ in range(N)]

def dfs(cur, pre) :
  s = 0
  for nex in vec[cur] :
    if nex == pre :
      continue
    t = dfs(nex, cur)
    s += t
    sub_size[cur].append(t)
  return s + 1

dfs(0, -1)

ret = 0
for i in range(N) :
  if sum(sub_size[i]) != N - 1 :
    sub_size[i].append(N - 1 - sum(sub_size[i]))
  
  if len(sub_size[i]) <= 1 :
    continue

  a, b = 1, 1
  for ss in sub_size[i] :
    x = pow(2, ss, mod)
    a *= pow(x, mod - 2, mod)
    b += x - 1
    a %= mod
    b %= mod
  ret += (1 - a * b) % mod
  ret %= mod

ret = ret * pow(2, mod - 2, mod) % mod

print(ret)

Submission status: Time Limit Exceeded

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

#dp=子ノードの数+1(自分)
dp=[1]*N

root=0
parent=[0]*N
order=[]
def dfs():
    parent[root]=root
    stack=[root]
    while stack:
        node=stack.pop()
        order.append(node)
        for ss in E[node]:
            if parent[node]!=ss:
                stack.append(ss)
                parent[ss]=node

def solve():
    ans=0
    inv2=pow(2,MOD-2,MOD)
    #p0=すべての部分木に黒頂点が1つも含まれない確率
    p0=pow(pow(2,N-1,MOD),MOD-2,MOD)
    for i in reversed(order):
        if root!=i:
            dp[parent[i]]+=dp[i]
        p=0
        if len(E[i])>=2:
            #p0*(p1-1)=どれか1つの各部分木に黒頂点が1つ以上含まれる確率
            p1=1
            for s in E[i]:
                size=0
                if parent[i]!=s:
                    size=dp[s]
                elif i!=root:
                    size=N-dp[i]
                else:
                    continue
                p1+=pow(2,size,MOD)-1
            p=1-(p0*p1)
            p%=MOD
        ans+=p
        ans%=MOD
    #頂点iが白の確率
    ans=ans*inv2%MOD
    print(ans)

dfs()
solve()

Submission status: Time Limit Exceeded

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

#dp=子ノードの数+1(自分)
dp=[1]*N

root=0
parent=[0]*N
order=[]
def dfs():
    parent[root]=root
    stack=[root]
    while stack:
        node=stack.pop()
        order.append(node)
        for ss in E[node]:
            if parent[node]!=ss:
                stack.append(ss)
                parent[ss]=node

def solve():
    ans=0
    inv2=pow(2,MOD-2,MOD)
    #p0=すべての部分木に黒頂点が1つも含まれない確率
    p0=pow(pow(2,N-1,MOD),MOD-2,MOD)
    for i in reversed(order):
        if root!=i:
            dp[parent[i]]+=dp[i]
        p=0
        if len(E[i])>=2:
            #p0*(p1-1)=どれか1つの各部分木に黒頂点が1つ以上含まれる確率
            p1=1
            for s in E[i]:
                size=0
                if parent[i]!=s:
                    size=dp[s]
                elif i!=root:
                    size=N-dp[i]
                else:
                    continue
                p1+=(1<<size)-1
                p1%=MOD
            p=1-(p0*p1)
            p%=MOD
        ans+=p
        ans%=MOD
    #頂点iが白の確率
    ans=ans*inv2%MOD
    print(ans)

dfs()
solve()

Submission status: Time Limit Exceeded

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

#dp=子ノードの数+1(自分)
dp=[1]*N

root=0
parent=[0]*N
order=[]
def dfs():
    parent[root]=root
    stack=[root]
    while stack:
        node=stack.pop()
        order.append(node)
        for ss in E[node]:
            if parent[node]!=ss:
                stack.append(ss)
                parent[ss]=node

def solve():
    ans=0
    inv2=pow(2,MOD-2,MOD)
    #p0=すべての部分木に黒頂点が1つも含まれない確率
    p0=pow((1<<(N-1))%MOD,MOD-2,MOD)
    for i in reversed(order):
        if root!=i:
            dp[parent[i]]+=dp[i]
        p=0
        if len(E[i])>=2:
            #p0*(p1-1)=どれか1つの各部分木に黒頂点が1つ以上含まれる確率
            p1=1
            for s in E[i]:
                size=0
                if parent[i]!=s:
                    size=dp[s]
                elif i!=root:
                    size=N-dp[i]
                else:
                    continue
                p1+=(1<<size)-1
                p1%=MOD
            p=1-(p0*p1)
            p%=MOD
        ans+=p
        ans%=MOD
    #頂点iが白の確率
    ans=ans*inv2%MOD
    print(ans)

dfs()
solve()

Submission status: Time Limit Exceeded

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)
 
E=[[] for _ in range(N)]
for A,B in AB:
    E[A-1].append(B-1)
    E[B-1].append(A-1)
MOD=10**9+7

#dp=子ノードの数+1(自分)
dp=[1]*N

root=0
parent=[0]*N
order=[]
def dfs():
    parent[root]=root
    stack=[root]
    while stack:
        node=stack.pop()
        order.append(node)
        for ss in E[node]:
            if parent[node]!=ss:
                stack.append(ss)
                parent[ss]=node

def solve():
    ans=0
    inv2=pow(2,MOD-2,MOD)
    #p0=すべての部分木に黒頂点が1つも含まれない確率
    p0=pow(1<<(N-1),MOD-2,MOD)
    for i in reversed(order):
        if root!=i:
            dp[parent[i]]+=dp[i]
        p=0
        if len(E[i])>=2:
            #p0*(p1-1)=どれか1つの各部分木に黒頂点が1つ以上含まれる確率
            p1=1
            for s in E[i]:
                size=0
                if parent[i]!=s:
                    size=dp[s]
                elif i!=root:
                    size=N-dp[i]
                else:
                    continue
                p1+=(1<<size)-1
                p1%=MOD
            p=1-(p0*p1)
            p%=MOD
        ans+=p
        ans%=MOD
    #頂点iが白の確率
    ans=ans*inv2%MOD
    print(ans)

dfs()
solve()

Submission status: Time Limit Exceeded

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

#dp=子ノードの数+1(自分)
dp=[1]*N

root=0
parent=[0]*N
order=[]
def dfs():
    parent[root]=root
    stack=[root]
    while stack:
        node=stack.pop()
        order.append(node)
        for ss in E[node]:
            if parent[node]!=ss:
                stack.append(ss)
                parent[ss]=node

def solve():
    ans=0
    inv2=pow(2,MOD-2,MOD)
    #p0=すべての部分木に黒頂点が1つも含まれない確率
    p0=pow(1<<(N-1),MOD-2,MOD)
    for i in reversed(order):
        if root!=i:
            dp[parent[i]]+=dp[i]
        p=0
        if len(E[i])>=2:
            #p0*(p1-1)=どれか1つの各部分木に黒頂点が1つ以上含まれる確率
            p1=1
            for s in E[i]:
                size=0
                if parent[i]!=s:
                    size=dp[s]
                elif i!=root:
                    size=N-dp[i]
                else:
                    continue
                p1+=(1<<size)-1
                p1%=MOD
            p=1-(p0*p1)
            p%=MOD
        ans+=p
        ans%=MOD
    #頂点iが白の確率
    ans=ans*inv2%MOD
    print(ans)

dfs()
solve()

Submission status: Time Limit Exceeded

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

#dp=子ノードの数+1(自分)
root=0
dp=[1]*N
parent=[0]*N
order=[]
def dfs():
    parent[root]=root
    stack=[root]
    while stack:
        node=stack.pop()
        order.append(node)
        for ss in E[node]:
            if parent[node]!=ss:
                stack.append(ss)
                parent[ss]=node

def solve():
    ans=0
    inv2=pow(2,MOD-2,MOD)
    #p0=すべての部分木に黒頂点が1つも含まれない確率
    p0=pow(1<<(N-1),MOD-2,MOD)
    for i in reversed(order):
        if root!=i:
            dp[parent[i]]+=dp[i]
        p=0
        if len(E[i])>=2:
            #p0*(p1-1)=どれか1つの各部分木に黒頂点が1つ以上含まれる確率
            p1=1
            for s in E[i]:
                size=0
                if parent[i]!=s:
                    size=dp[s]
                elif i!=root:
                    size=N-dp[i]
                else:
                    continue
                p1+=(1<<size)-1
                p1%=MOD
            p=1-(p0*p1)
            p%=MOD
            #頂点iが白の確率
            p=p*inv2%MOD
        ans+=p
        ans%=MOD
    print(ans)

dfs()
solve()