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:
n = int(input())
peer = [[] for _ in range(n)]
for _ in range(n-1):
  a,b = map(int,input().split())
  a -= 1
  b -= 1
  peer[a].append(b)
  peer[b].append(a)
pre = [10**6 for _ in range(n)]
pre[0] = -1
pst = [[] for _ in range(n)]
rank = [[0]]
seen = [0 for _ in range(n)]
seen[0] = 1
now = [0]
while now:
  last = now
  now = []
  for x in last:
    for y in peer[x]:
      if seen[y] == 0:
        seen[y] = 1
        now.append(y)
        pre[y] = x
        pst[x].append(y)
  rank.append(now)
rank = rank[1:-1]
#print(rank)

family = [1 for _ in range(n)]
rank.reverse()
for z in rank:
  for w in z:
    family[pre[w]] += family[w]
#print(pre)
#print(family)

mod = 10**9+7
half = 5*10**8+4
satoshi = 1
btc = [1]
for _ in range(n):
  satoshi *= half
  satoshi %= mod
  btc.append(btc[-1]*2%mod)
#print(satoshi,btc)

ans = 0
for i in range(n):
  if i == 0:
    if len(pst[i]) == 1:
      pass
    else:
      q = []
      for x in pst[i]:
        q.append(family[x])
      tmp = -len(q)+1
      for p in q:
        tmp += btc[p]
      tmp = btc[n-1] - tmp
      #print(tmp)
      ans += tmp
  else:
    if len(pst[i]) == 0:
      pass
    else:
      q = []
      for x in pst[i]:
        q.append(family[x])
      q.append(n-1-sum(q))
      tmp = -len(q)+1
      for p in q:
        tmp += btc[p]
      tmp = btc[n-1] - tmp
      #print(tmp)
      ans += tmp
  #try:
    #print(i,q)
  #except:
    #pass
ans *= satoshi
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)
readline = sys.stdin.readline

N = int(readline())

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

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

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)
    ans %= mod
    
    return cnt

dfs(0, None)

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

print(ans)

Submission status: Accepted

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

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

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

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

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

print(ans)

Submission status: Accepted

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

N = int(readline())
graph = [[] for _ in range(N + 1)]
for i in range(N - 1):
    a, b = map(int, readline().split())
    lb = 1 << i
    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)

MOD = 10**9 + 7
x = (MOD + 1) // 2
power_inv = [1] * (N + 100)
for i in range(1, N + 100):
    power_inv[i] = power_inv[i - 1] * x % MOD

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

ans = 0
for i in size[2:]:
    ans += 1 - power_inv[i] - power_inv[N - i] + power_inv[N]
    ans %= MOD
ans = ans - N * power_inv[1] + 1 - power_inv[N]
ans %= MOD

print(ans)

Submission status: Accepted

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 = [1] * (N + 1)
for i, j in zip(range(N), range(1, N + 1)):
    pow2[j] = pow2[i] * 2 % mod

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)
    ans %= mod
    
    return cnt

dfs(0, None)

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

print(ans)

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(2 * (10 ** 5))

n = int(input())
ab = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(n-1)]

e = [[] for _ in range(n)]

for a, b in ab:
    e[a].append(b)
    e[b].append(a)

MOD = 10 ** 9 + 7

d = []

def modinv(x):
    a = x
    b = MOD
    u = 1
    v = 0
    while b:
        t = a // b
        a -= t * b
        a, b = b, a
        u -= t * v
        u, v = v, u
    u %= MOD
    if u < 0:
        u += MOD
    return u

def dfs(x, p):
    if len(e[x]) == 1:
        if e[x][0] == p:
            d.append(1)
            return 1
    ret = 1
    for z in e[x]:
        if z == p:
            continue
        ret += dfs(z, x)
    if x != 0:
        #print(x, d)
        d.append(ret)
    return ret

dfs(0,-1)

f = []
w = 1
for i in range(n + 1):
    f.append(w)
    w = (w * 2) % MOD

#print(d)

ans = 0
for x in d:
    ans += ((f[x] - 1) * (f[n-x] - 1)) % MOD
    ans %= MOD

#print(ans)

ans = (ans - f[n-1] * n + f[n] - 1 + MOD) % MOD

#print(ans)

ans = (ans * modinv(f[n])) % MOD

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200200)
input = sys.stdin.readline
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: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
import sys
import math
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
mod = 1000000007

def solve():
    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)
    q = deque([0])
    d = [0]*n
    d[0] = 1
    pre = [None]*n
    while q:
        x = q.popleft()
        nd = d[x]+1
        for y in v[x]:
            if not d[y]:
                d[y] = nd
                pre[y] = x
                q.append(y)
    V = list(range(1,n))
    V.sort(key = lambda x:-d[x])
    size = [1]*n
    for i in V:
        size[pre[i]] += size[i]
    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[i]
        b = n-a
        ans += (p[a]-1)*(p[b]-1)%mod
        ans %= mod
    print(ans)
    return

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

Submission status: Accepted

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():
    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)
    q = deque([0])
    d = [0]*n
    d[0] = 1
    pre = [None]*n
    while q:
        x = q.popleft()
        nd = d[x]+1
        for y in v[x]:
            if not d[y]:
                d[y] = nd
                pre[y] = x
                q.append(y)
    V = list(range(1,n))
    V.sort(key = lambda x:-d[x])
    size = [1]*n
    for i in V:
        size[pre[i]] += size[i]
    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[i]
        b = n-a
        ans += (p[a]-1)*(p[b]-1)%mod
        ans %= mod
    print(ans)
    return

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

Submission status: Accepted

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


def main():
    mod = 10**9+7
    n = int(input())
    edge = [[] for _ in [0]*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)
    
    #root
    p = -1
    ma = -1
    for i in range(n):
        if len(edge[i]) > ma:
            p = i
            ma = len(edge[i])

    #parent
    par = [-2]*n
    par[p] = -1
    order = []
    tank = [p]
    while tank:
        x = tank.pop()
        order.append(x)
        for elt in edge[x]:
            if par[elt] == -2:
                par[elt] = x
                tank.append(elt)
        

    #size
    size = [1]*n    
    for i in range(n-1,0,-1):
        now = order[i]
        size[par[now]] += size[now]
    
    se_N1 = pow(2,n-1,mod)

    res = 0
    for i in range(n):
        if size[i] == 1:
            continue
        #size list
        Q = []
        for elt in edge[i]:
            if elt == par[i]:
                Q.append(n-size[i])
            else:
                Q.append(size[elt])
        res = (res + se_N1)%mod
        cpm = 1
        for e in Q:
            cpm = (cpm + pow(2,e,mod) - 1)%mod
        res = (res-cpm)%mod

    print(res*pow(2,n*(mod-2),mod)%mod) 

    





if __name__ == '__main__':
    main()

Submission status: Accepted

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)
y = I.invx(PM.F[N])

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 * y) % MOD

print(ans)

Submission status: Accepted

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

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

POW2=[1]
for i in range(N+1):
    POW2.append(POW2[-1]*2%mod)

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+=POW2[s]-1

    ANS+=POW2[N-1]-AV
    #print(SCORE,AV)

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

Submission status: Accepted

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

POW2=[1]
for i in range(N+1):
    POW2.append(POW2[-1]*2%mod)

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+=POW2[s]-1

    ANS+=POW2[N-1]-AV
    #print(SCORE,AV)

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

Submission status: Accepted

Solution code:
import sys
import math
import heapq
sys.setrecursionlimit(10**7)
INTMAX = 9223372036854775807
INTMIN = -9223372036854775808
DVSR = 1000000007
def POW(x, y): return pow(x, y, DVSR)
def INV(x, m=DVSR): return pow(x, m - 2, m)
def DIV(x, y, m=DVSR): return (x * INV(y, m)) % m
def LI(): return [int(x) for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()
def II(): return int(input())
def FLIST(n):
    res = [1]
    for i in range(1, n+1): res.append(res[i-1]*i%DVSR)
    return res
def gcd(x, y):
    if x < y: x, y = y, x
    div = x % y
    while div != 0:
        x, y = y, div
        div = x % y
    return y

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

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 = (DVSR + 1) // 2
PWR=[1]*(N+1)
RWP=[1]*(N+1)

for i in range(1,N+1):
    PWR[i] = PWR[i-1] * 2 % DVSR
    RWP[i] = RWP[i-1] * x % DVSR

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 *= RWP[x]
        prod %= DVSR
        coef += (PWR[x] - 1)
    E = 1 - prod * coef % DVSR
    answer += E

answer *= RWP[1]
answer %= DVSR
print(answer)

Submission status: Accepted

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 = [1] * N
B[-1] = pow(1 << (N - 1), p - 2, p)
for i in range(N - 1, 0, -1):
  B[i - 1] = B[i] * 2 % p
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: Accepted

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)

own_size = [0] * N
sub_size = [[] for _ in range(N)]

# pythonのdfs重すぎて自分でstack書かないと通らない。
# く〜〜つらいとこね、これ！！！！
stack = [(0, -1)]
for i in range(N) :
  cur, pre = stack[i]
  for nex in vec[cur] :
    if nex != pre :
      stack.append((nex, cur))

while stack :
  cur, pre = stack.pop()
  if pre != -1 :
    sub_size[pre].append(own_size[cur] + 1)
    own_size[pre] += own_size[cur] + 1
  if own_size[cur] != N - 1 :
    sub_size[cur].append(N - 1 - own_size[cur])

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: Accepted

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

mod = 10**9+7

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

#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m=mod):
    x = extgcd(a,m)[0]
    return (m+x%m)%m


N2 = [1]
n = 1
for _ in range(N+1):
    n = n*2 % mod
    N2.append(n)

Weight = [[] for _ in range(N)]
checked = [False]*N

def dfs(p):
    checked[p] = True
    downs = 0
    for np in graph[p]:
        if not checked[np]:
            downscore = dfs(np)
            Weight[p].append(N-downscore)
            Weight[np].append(downscore)
            downs += N-downscore
    
    return N-(downs+1)

dfs(0)

a = 0
for n in range(N):
    if len(Weight[n]) == 1:
        continue
    c = N2[N-1] - 1
    for w in Weight[n]:
        c = (c - N2[w] + 1) % mod
    a = (a + c) % mod

ans = (a * mod_inv(N2[N])) % mod
print(ans)

Submission status: Accepted

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

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

def solve():
    ans=0
    inv2=pow(2,MOD-2,MOD)
    #p0=すべての部分木に黒頂点が1つも含まれない確率
    p0=pow(pow2[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+=pow2[size]-1
            p=1-(p0*p1)
            p%=MOD
        ans+=p
        ans%=MOD
    #頂点iが白の確率
    ans=ans*inv2%MOD
    print(ans)

dfs()
solve()

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI1(): return map(int1, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]

def main():
    def dfs(u=0, pu=-1):
        res = 1
        for cu in to[u]:
            if cu == pu: continue
            ret = dfs(cu, u)
            children_size[u].append(ret)
            res += ret
        return res

    md = 10 ** 9 + 7
    n = II()
    to = [[] for _ in range(n)]
    for _ in range(n - 1):
        a, b = MI1()
        to[a].append(b)
        to[b].append(a)
    #print(to)

    # 1/2をmodで表して、累乗を事前計算
    half = pow(2, md - 2, md)
    exp_half = [1, half]
    for _ in range(n):
        exp_half.append(exp_half[-1] * half % md)
    # print(exp_half)

    # 子の部分木のサイズ(要素数)をdfsで求める
    children_size = [[] for _ in range(n)]
    dfs()
    # print(children_size)

    # それぞれの頂点において、接続する部分木のうち
    # 2つ以上の部分木に黒が含まれる確率を求める
    # 余事象を利用(1-黒を含む部分木がない確率-黒を含む部分木が1つの確率)
    # (その頂点が白の確率)×(上記の確率)がその頂点が白で残る期待値なので和を求めれば答え
    ans = 0
    noblack = exp_half[n - 1]
    for cs in children_size:
        if not cs: continue
        sum_cs = sum(cs)
        if sum_cs != n - 1: cs.append(n - 1 - sum_cs)
        onlyone = 0
        for child_size in cs:
            onlyone += (1 - exp_half[child_size]) * exp_half[n - 1 - child_size]
        ans += (1 - noblack - onlyone) * half
        ans %= md
    print(ans)

main()

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


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)]
#
# N = 5
# AB = generate_tree(N, directed=False)
# AB = [(a + 1, b + 1) for a, b in AB]
# print(N)
# for a, b in AB:
#     print(a, b)
# plot_graph(AB)


# 解説
# 辺に着目すれば絶対2つに木を分割できるので計算が簡単になる

graph = [[] for _ in range(N)]
for a, b in AB:
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

# S の頂点数の期待値 - 黒の数の期待値
# 両側の部分木に黒がある場合、その辺は S に含まれる
root = 0
stack = [(0, None)]
hist = []
while stack:
    v, parent = stack.pop()
    hist.append((v, parent))
    for u in graph[v]:
        if u == parent:
            continue
        stack.append((u, v))

subtree_sizes = [0] * N
hist.reverse()
for v, parent in hist:
    ret = 0
    for u in graph[v]:
        if u == parent:
            continue
        ret += subtree_sizes[u]
    subtree_sizes[v] = ret + 1

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

# 辺の数の期待値 * 2**N
# すべてのパターンに含まれる辺の数の合計
e_exp = 0
for v in range(N):
    for u in graph[v]:
        if v < u:
            continue
        # 両側の頂点数
        s = min(subtree_sizes[v], subtree_sizes[u])
        t = N - s

        # 全部のパターン数から全部白のパターン数を引く
        cnt = pow2[N]
        # s が全部白のぱたーん数
        cnt -= pow2[t]
        # t が全部白のぱたーん数
        cnt -= pow2[s]
        # 引きすぎ
        cnt += 1
        e_exp += cnt
        e_exp %= MOD
# 頂点数は辺の数 + 1
# 全部白の場合空グラフになるので1つ減らす
v_exp = e_exp + pow2[N] - 1
ans = div_mod(v_exp, pow2[N], MOD) - div_mod(N, 2, MOD)
ans %= MOD
print(ans)
# print((v_exp / (2 ** N)) - N / 2)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
mod = 10**9+7
N = int(input())
g = [[] for _ in range(N)]
d = defaultdict(lambda:-1)
p2 = [1]*(N+1)
p2[1] = pow(2,mod-2,mod)
for i in range(N):
    p2[i+1] = (p2[i]*p2[1])%mod

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

q = deque([[a,b]])
while q:
    i,j = q.pop()
    s = 1
    f = True
    for k in g[j]:
        if k == i:
            continue
        if (j,k) not in d:
            if f:
                q.append([i,j])
            q.append([j,k])
            f = False
        else:
            s += d[(j,k)]
    if f:
        d[(i,j)] = s

q = deque([[b,a]])
while q:
    i,j = q.pop()
    s = 1
    f = True
    for k in g[j]:
        if k == i:
            continue
        if (j,k) not in d:
            if f:
                q.append([i,j])
            q.append([j,k])
            f = False
        else:
            s += d[(j,k)]
    if f:
        d[(i,j)] = s

ans = 1-p2[N]-N*p2[1]

for i in range(N):
    for j in g[i]:
        if j<i:
            continue
        n = max(d[(i,j)],d[(j,i)])
        ans += (1-p2[n])*(1-p2[N-n])
        ans %= mod

print(ans)

Submission status: Accepted

Solution code:
import sys


def dfs1(root, links):
    parent = [0] * n
    subtree_count = [{} for _ in range(n)]
    q = [(root, -1, 0)]  # 2番目:親  3番目:0=初, 1=全ての子巡回後
    while q:
        v, p, t = q.pop()
        if t == 0:
            parent[v] = p
            q.append((v, p, 1))
            for u in links[v]:
                if u == p:
                    continue
                q.append((u, v, 0))
        elif p != -1:
            subtree_count[p][v] = sum(subtree_count[v].values()) + 1
    return parent, subtree_count


def dfs2(root, parent, subtree_count, d2, d2s):
    ans = 0
    q = [(root, 0)]
    while q:
        v, pc = q.pop()

        if len(subtree_count[v]) == 0:
            continue

        p = parent[v]
        children, st_counts = map(list, zip(*subtree_count[v].items()))
        children.append(p)
        st_counts.append(pc)
        cl = len(st_counts)
        ct = sum(st_counts)

        for u, stc in subtree_count[v].items():
            q.append((u, ct - stc + 1))

        if cl == 1:
            continue

        tmp = 0
        for stc in st_counts:
            tmp = (tmp + d2s[ct - stc]) % MOD
        tmp = (tmp - d2s[ct] * (cl - 1)) % MOD
        ans = (ans + (1 - tmp) * d2) % MOD
    return ans


n = int(input())
links = [set() for _ in range(n)]
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
root = 0
MOD = 10 ** 9 + 7
d2 = 500000004  # 2^-1 mod 10**9+7
d2s = [1]
for i in range(n):
    d2s.append(d2s[-1] * d2 % MOD)
parent, subtree_count = dfs1(root, links)
# print(parent)
# print(subtree_count)
ans = dfs2(root, parent, subtree_count, d2, d2s)
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import deque
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
pow2 = [1]
for i in range(N + 10):
    pow2.append(pow2[-1] * 2 % mod)
inv2 = (mod + 1) // 2

invpow2 = [pow(pow2[-1], mod-2, mod)]
for i in range(N + 10)[::-1]:
    invpow2.append(invpow2[-1] * 2 % mod)
invpow2 = invpow2[::-1]

A = [1] * N
for i in R[::-1]:
    s = 0
    for j in X[i]:
        A[i] += A[j]

ans = 0
for i in range(N):
    s = pow(inv2, N - A[i], mod)
    t = 1 + (1-invpow2[N-A[i]]) * pow2[N-A[i]]
    for j in X[i]:
        s = (s * invpow2[A[j]]) % mod
        t = (t + (1-invpow2[A[j]]) * pow2[A[j]]) % mod
    ans = (ans + 1 - s * t) % mod

print(ans * inv2 % mod)