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
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal
from argparse import ArgumentParser

args=ArgumentParser()
args.add_argument('-loc', '--local', type=bool,default=False)
LOCAL=args.parse_args().local

def input(): 
    x=sys.stdin.readline(); 
    if x[-1]=="\n": 
        return x.rstrip() 
    return x
    
def printe(*x):_=print("## ",*x,file=sys.stderr) if LOCAL else 0
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

class rerooting:#全方位木
    def __init__(self,N,edge):#単位元self.unitとモノイドdef func,および親の追加処理def addnode設定すること
        #tot[親]:すべての子の値の累計
        #dics[親][根（親の隣接点)]=その部分木での値
        self.unit=0
        self.edge=edge
        self.par=[-1]*N
        self.N=N
        self.visited=[0]*N
        self.dics=[dict() for _ in range(N)]
        self.ikigake=[]
        self.tot=[self.unit]*N
        self._forward(0)
        

    def func(self,x,y):
        return x+y

    def addnode(self,x):#辺(距離)に関するdpのとき必要
        return x+1

    def _dfs(self,start):
        edge=self.edge
        N=self.N
        par=self.par
        q=deque([(start,start)])
        while len(q):
            e,pa=q.pop()#ここをpopleftにすると幅優先探索BFSになる
            if par[e]!=-1:continue
            par[e]=pa
            self.ikigake.append(e)
            for ne in edge[e]:q.append((ne,e))
        
        for e in reversed(self.ikigake[1:]):
            pa=par[e]
            ans=self.unit
            de=self.dics[e]
            for val in de.values():
                ans=self.func(ans,val)
            self.dics[pa][e]=self.addnode(ans)
    
    def _forward(self,start):
        self._dfs(start)
        for e in self.ikigake:
            pa=self.par[e]
            nes=list(self.dics[e].keys())
            nvals=list(self.dics[e].values())
            l=len(nes)
            aleft=[self.unit]
            aright=[self.unit]
            for i in range(l-1):
                aleft.append(self.func(aleft[-1],nvals[i]))
                aright.append(self.func(aright[-1],nvals[-i-1]))
            
            for i,ne in enumerate(nes):
                if ne==pa:
                    continue
                self.dics[ne][e]=self.addnode(self.func(aleft[i],aright[-1-i]))

            self.tot[e]=self.func(aright[-1],nvals[0])
        return self.dics

def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    edge = [[] for i in range(N)]
    for i in range(N-1):#木の場合M=N-1
        a,b= map(int,input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1) #有向のばあいコメントアウト

    rt=rerooting(N,edge)
    d=rt.dics
    tot=rt.tot
    
    i2=pow(2,mod-2,mod)
    i2n=pow(i2,N,mod)
    i2n1=pow(i2,N-1,mod)
    ans=0
    cur0=(i2-i2n)%mod
    p2=[pow(2,i,mod) for i in range(N+1)]

    for i in range(N):
        if len(edge[i])<2:
            continue
        cur=cur0
        
        for ne in d[i].values():
            cur-=(p2[ne]-1)*i2n
        
        ans+=cur
        ans%=mod
    
    print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

"""
ある頂点が白のとき，穴あき度の総和に与える影響を考える，
入力例2の1-2-3-4なら(0,3,3,0)この頂点2に注目，この3は，上下どちらもに黒があれば良い．上(2^1 - 1) * 下(2^2 - 1)=3．つまり全量 - all白

実際には子が多い．どこか2箇所の部分木に黒があれば良い=>余事象．
・全量：pow(2,N-1)，自分は白確定，墓はなんでも良い

・all白=1通り
・1個の部分木が黒*1通り（*1は残りall白の分）
「1この部分木が黒」はどう求める？　その部分木のサイズをnとして，2^n - 1．
その部分木のサイズはどう求める？　全方位木DPか=>端の頂点から詰めていけばいけそう

"""

def main():
    mod=10**9+7
    import queue
        
    N=I()
    adj=[[]for _ in range(N)]
    for i in range(N-1):
        x,y=MI()
        x-=1
        y-=1
        adj[x].append(y)
        adj[y].append(x)
        
    #2べきを持っておくか，
    POW=[1]
    for _ in range(N+5):
        temp=POW[-1]
        POW.append((temp*2)%mod)
        
    #各頂点のじすう
    deg=[0]*N
    for i in range(N):
        deg[i]=len(adj[i])
    
    
    L=[[]for _ in range(N)]#　各頂点からみて，個を根とする部分木のサイズを配列として持っておく    
    
    looked=[0]*N#qに突っ込むか
    used=[0]*N#計算を終えたか
    q=queue.Queue()
    
    for v in range(N):
        if len(adj[v])==1:
            q.put(v)
            L[v].append(0)
            looked[v]=1
            
    ans=[0]*N
    while not q.empty():
        v=q.get()
        
        S=sum(L[v])
        rem=(N-1)-S#まだ見ていない方向の合計，-1は自分自身
        temp=POW[N-1]#全体
        temp-=1#all白
        
        for s in L[v]:#1つの部分木にだけ黒があるパターンを引く
            temp-=POW[s]-1
            temp%=mod
            
        #1つの部分木にだけ黒があるパターンを引く，続き
        temp-=POW[rem]-1
        temp%=mod
            
        ans[v]=temp
        used[v]=1
        
        for nv in adj[v]:
            if used[nv]==0:
                L[nv].append(S+1)
            
            if looked[nv]==0:
                # nvの計算に必要な方向をしっかり見ていれば計算用のqに回す
                if len(L[nv])>=deg[nv]-1:
                    q.put(nv)
                    looked[nv]=1
                
                
    # print(ans)
    
    y=sum(ans)
    x=POW[N]
    
    res=(y*pow(x,mod-2,mod))%mod
    print(res)
    
        
    
        
    
    

main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)
input = sys.stdin.readline
N = int(input()); MOD=pow(10,9)+7

beki = [-1]*(N+1); beki[0] = 1; beki[1] = 2 #階乗
for i in range(2,N+1):
  beki[i] = beki[i-1]*2%MOD
#print(beki)

G = [[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int,input().split())
  a-=1;b-=1
  G[a].append(b);G[b].append(a)
#print(G)
ans = 0

def dfs(v,p): #自分と親
  global ans #ansをGlobal変数として宣言
  res = 1 #戻り値。vを含めた部分木のサイズ。自分の分で最初は1
  ts = [] #vから生えている部分木のリスト
  for u in G[v]:
    if u == p:
      continue
    t = dfs(u,v) #uの部分木のサイズが戻り値
    res += t
    ts.append(t)
  if p != -1: #根以外なら親側の部分木が存在する。
    ts.append(N-res)
  now = beki[N-1] - 1 #自分以外を決めるのが2^(N-1)通り。自分以外が全部0が1通り。
  for x in ts:
    now -= beki[x] - 1 #各部分木に一個以上黒がある場合の数。全通り - 全部白
  ans = (ans+now)%MOD
  return res #vを含めた部分木のサイズ

dfs(0,-1)
ALL = pow(2,N,MOD)
#print(ans,ALL)
ans = ans*pow(ALL,MOD-2,MOD)%MOD #フェルマーの小定理より1/ALL = ALL^(MOD-2)
print(ans)

Submission status: Accepted

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

mod = 10**9+7

def dfs(graph, N):
    ans = 0
    Par = [-1]*N
    Childs = [[] for _ in range(N)]
    stack = [0]
    while stack:
        p = stack.pop()
        if p >= 0:
            stack.append(~p)
            for np in graph[p]:
                if np != 0 and Par[np] == -1:
                    stack.append(np)
                    Par[np] = p
        else:
            p = ~p
            score = pow(2, N-1, mod) - 1
            upper = N-1
            for a in Childs[p]:
                upper -= a
                score = (score - pow(2, a, mod) + 1) % mod
            if p != 0:
                score = (score - pow(2, upper, mod) + 1) % mod
            ans = (ans + score) % mod
            Childs[Par[p]].append(N-1-upper+1)
    
    return ans * pow(2, N*(mod-2), mod) % mod

def main():
    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)
    print(dfs(graph, N))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2*10**5)
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: Accepted

Solution code:
# classを使うのをやめてlistで実施する
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

def dfs(v):
    visited[v] = True
    for i in range(len(AL[v][CHILDREN])):
        u = AL[v][CHILDREN][i]
        if visited[u]:
            AL[v][CHILDREN][i] = None
            continue
        AL[v][SIZE] += dfs(u)
    return AL[v][SIZE]

def anaaki(v):
    ret = powp - 1
    for ch in AL[v][CHILDREN]:
        if ch is None: continue
        ret -= pow(2, AL[ch][SIZE], p) - 1
        ret %= p
    ret -= pow(2, n - AL[v][SIZE], p) - 1
    ret %= p
    return ret

n = int(input())
SIZE = 0
CHILDREN = 1
AL = [[1, []] for _ in range(n)]
visited = [False] * n
p = 10 ** 9 + 7
powp = pow(2, n - 1, p)

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

dfs(0)
numer = 0
for i in range(n):
    numer += anaaki(i)
    numer %= p

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

Submission status: Accepted

Solution code:
# classを使うのをやめてlistで実施する
from collections import deque
import sys
sys.setrecursionlimit(10 ** 9)
import sys
input = sys.stdin.readline

def dfs(v):
    visited[v] = True
    for i in range(len(AL[v][CHILDREN])):
        u = AL[v][CHILDREN][i]
        if visited[u]:
            AL[v][CHILDREN][i] = None
            continue
        AL[v][SIZE] += dfs(u)
    return AL[v][SIZE]


def anaaki(v):
    ret = powp - 1
    for ch in AL[v][CHILDREN]:
        if ch is None: continue
        ret -= pow(2, AL[ch][SIZE], p) - 1
        ret %= p
    ret -= pow(2, n - AL[v][SIZE], p) - 1
    ret %= p
    return ret

n = int(input())
SIZE = 0
CHILDREN = 1
AL = [[1, []] for _ in range(n)]
visited = [False] * n
p = 10 ** 9 + 7
powp = pow(2, n - 1, p)

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

dfs(0)
numer = 0
for i in range(n):
    numer += anaaki(i)
    numer %= p

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

Submission status: Accepted

Solution code:
class Tree():
    def __init__(self, n, edge, indexed=1):
        self.n = n
        self.tree = [[] for _ in range(n)]
        for e in edge:
            self.tree[e[0] - indexed].append(e[1] - indexed)
            self.tree[e[1] - indexed].append(e[0] - indexed)

    def setroot(self, root):
        self.root = root
        self.parent = [None for _ in range(self.n)]
        self.parent[root] = -1
        self.depth = [None for _ in range(self.n)]
        self.depth[root] = 0
        self.order = []
        self.order.append(root)
        self.size = [1 for _ in range(self.n)]
        stack = [root]
        while stack:
            node = stack.pop()
            for adj in self.tree[node]:
                if self.parent[adj] is None:
                    self.parent[adj] = node
                    self.depth[adj] = self.depth[node] + 1
                    self.order.append(adj)
                    stack.append(adj)
        for node in self.order[::-1]:
            for adj in self.tree[node]:
                if self.parent[node] == adj:
                    continue
                self.size[node] += self.size[adj]

import sys
input = sys.stdin.readline

MOD = 1000000007

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

t = Tree(N, E)
t.setroot(0)

res = 0

for node in range(N):
    tmp = pow(2, N - 1, MOD) - 1
    for adj in t.tree[node]:
        if t.parent[node] == adj:
            s = N - t.size[node]
        else:
            s = t.size[adj]
        tmp -= pow(2, s, MOD) - 1
        tmp %= MOD
    res += tmp
    res %= MOD

res *= pow(pow(2, N, MOD), MOD - 2, MOD)
res %= MOD

print(res)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys


sys.setrecursionlimit(10 ** 6)


def ext_euc(a, b):
    if b == 0:
        return 1, 0, a
    y, x, v = ext_euc(b, a % b)
    y -= (a // b) * x
    return x, y, v


def mod_inv(a, mod):
    x, _, _ = ext_euc(a, mod)
    return x % mod


def main():
    MOD = 10 ** 9 + 7
    N = int(input())
    adj = defaultdict(list)
    for _ in range(N - 1):
        A, B = list(map(lambda x: int(x) - 1, input().split()))
        adj[A].append(B)
        adj[B].append(A)

    # 2 ** n の事前計算
    pow_2 = [1 for _ in range(N + 1)]
    for i in range(1, N + 1):
        pow_2[i] = pow_2[i - 1] * 2 % MOD

    # 分子：sum_{i} (node i が穴あき度の値としてカウント対象になるような塗り方)
    # node_num[(node, dir_node)]: nodeから見てdir_node方向に存在するノードの数
    #         5               6
    #        (6)             (6)
    #         |               |
    #        (1)             (1)
    # 0(6)-(1)1(4)-(3)2(3)-(4)3(1)-(6)4
    node_num = defaultdict(int)

    def dfs(node=0, parent=None):
        child_list = [n for n in adj[node] if n != parent]
        if len(child_list) == 0:
            node_num[(node, parent)] = N - 1
            node_num[(parent, node)] = 1
            return 1
        n_descendant = 1  # self
        for child in child_list:
            n_descendant += dfs(child, node)
        if parent is not None:
            node_num[(node, parent)] = N - n_descendant
            node_num[(parent, node)] = n_descendant
        return n_descendant

    dfs()

    numer = 0
    for node in range(N):
        if len(adj[node]) <= 1:
            # 端（次数1）のノードはカウント対象にならない
            continue
        cnt_not = 0  # node が穴あき度の値としてカウントされないケース
        for dir_node in adj[node]:
            # dir_node方向のノードは自由、それ以外の方向のノードは全部白
            cnt_not += pow_2[node_num[(node, dir_node)]]
        cnt_not -= len(adj[node]) - 1  # 「全部白塗り」の重複カウントを除去
        numer += pow_2[N - 1] - cnt_not  # node自身は白でないとカウントされないので、全体のパターン数が2 ** (N-1)

    # 分母：2 ** N （全部の塗り方）
    denom = pow_2[N]

    # 答え
    print(numer * mod_inv(denom, MOD) % MOD)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import os
import sys
import numpy as np

def solve(N, AB):
    mod = 10**9+7
    half = mod // 2 + 1
    G = [[0]*0 for _ in range(N+1)]
    for i in range(len(AB)):
        a, b = AB[i]
        G[a].append(b)
        G[b].append(a)
    P = np.zeros(N+1, dtype=np.int64)
    Size = np.zeros(N+1, dtype=np.int64)
    def dfs(v):
        # siz = 1
        # p = P[v]
        # for u in G[v]:
        #     if u != p:
        #         P[u] = v
        #         dfs(u)
        #         siz += Size[u]
        # Size[v] = siz
        st = [(v, 0)]
        while st:
            v, state = st.pop()
            p = P[v]
            if state == 0:
                st.append((v, 1))
                Size[v] = 1
                for u in G[v]:
                    if u != p:
                        P[u] = v
                        st.append((u, 0))
            else:
                Size[p] += Size[v]
    dfs(1)
    ans = 0
    Prob = np.empty(202020, dtype=np.int64)
    h = 1
    for i in range(202020):
        Prob[i] = 1-h+mod
        h = h * half % mod
    for v in range(1, len(G)):
        siz_v = Size[v]
        Gv = G[v]
        if v == 1:
            ps = [0]*0
        else:
            ps = [Prob[N-siz_v]]
        par = P[v]
        for u in Gv:
            if par != u:
                siz_u = Size[u]
                ps.append(Prob[siz_u])
        if len(ps)<=1:
            continue
        cumprod1_ps = [1, 1]
        cumprod2_ps = [1, 1]
        cp = 1
        for p in ps:
            cp = cp * (1-p+mod) % mod
            cumprod1_ps.append(cp)
        cp = 1
        for p in ps[::-1]:
            cp = cp * (1-p+mod) % mod
            cumprod2_ps.append(cp)
        cumprod2_ps.reverse()
        an = 1 - cumprod1_ps[-1]
        for j in range(1, len(cumprod1_ps)-1):
            cp1 = cumprod1_ps[j]
            cp2 = cumprod2_ps[j]
            p = ps[j-1]
            an -= cp1 * cp2 % mod * p % mod
        ans += an
    ans = ans % mod * half % mod
    return ans


# >>> numba compile >>>
numba_config = [
    [solve, "i8(i8,i8[:,:])"],
]
if sys.argv[-1] == "ONLINE_JUDGE":
    from numba import njit
    from numba.pycc import CC
    cc = CC("my_module")
    for func, signature in numba_config:
        vars()[func.__name__] = njit(signature)(func)
        cc.export(func.__name__, signature)(func)
    cc.compile()
    exit()
elif os.name == "posix":
    exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
else:
    from numba import njit
    for func, signature in numba_config:
        vars()[func.__name__] = njit(signature, cache=True)(func)
    print("compiled!", file=sys.stderr)
# <<< numba compile <<<


def main():
    sys.setrecursionlimit(505050)
    input = sys.stdin.buffer.readline
    N = int(input())
    AB = np.array(sys.stdin.buffer.read().split(), dtype=np.int64).reshape(N - 1, 2)
    ans = solve(N, AB)
    print(ans)

main()

Submission status: Accepted

Solution code:
import os
import sys
import numpy as np

def solve(N, AB):
    mod = 10**9+7
    half = mod // 2 + 1
    G = [[0]*0 for _ in range(N+1)]
    for i in range(len(AB)):
        a, b = AB[i]
        G[a].append(b)
        G[b].append(a)
    P = [0] * (N+1)
    Size = [0] * (N+1)
    def dfs(v):
        # siz = 1
        # p = P[v]
        # for u in G[v]:
        #     if u != p:
        #         P[u] = v
        #         dfs(u)
        #         siz += Size[u]
        # Size[v] = siz
        st = [(v, 0)]
        while st:
            v, state = st.pop()
            p = P[v]
            if state == 0:
                st.append((v, 1))
                Size[v] = 1
                for u in G[v]:
                    if u != p:
                        P[u] = v
                        st.append((u, 0))
            else:
                Size[p] += Size[v]
    dfs(1)
    ans = 0
    Prob = [0]
    h = 1
    for i in range(202020):
        h = h * half % mod
        Prob.append(1-h)
    for v in range(1, len(G)):
        siz_v = Size[v]
        Gv = G[v]
        if v == 1:
            ps = [0]*0
        else:
            ps = [Prob[N-siz_v]]
        par = P[v]
        for u in Gv:
            if par != u:
                siz_u = Size[u]
                ps.append(Prob[siz_u])
        if len(ps)<=1:
            continue
        cumprod1_ps = [1, 1]
        cumprod2_ps = [1, 1]
        cp = 1
        for p in ps:
            cp = cp * (1-p) % mod
            cumprod1_ps.append(cp)
        cp = 1
        for p in ps[::-1]:
            cp = cp * (1-p) % mod
            cumprod2_ps.append(cp)
        cumprod2_ps.reverse()
        an = 1 - cumprod1_ps[-1]
        for j in range(1, len(cumprod1_ps)-1):
            cp1 = cumprod1_ps[j]
            cp2 = cumprod2_ps[j]
            p = ps[j-1]
            an -= cp1 * cp2 % mod * p
        ans += an
    ans = ans % mod * half % mod
    return ans


def main():
    sys.setrecursionlimit(505050)
    input = sys.stdin.buffer.readline
    N = int(input())
    AB = np.array(sys.stdin.buffer.read().split(), dtype=np.int64).reshape(N - 1, 2)
    ans = solve(N, AB)
    print(ans)

main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(505050)
input = sys.stdin.buffer.readline
N = int(input())
AB = [list(map(int, input().split())) for _ in range(N-1)]
mod = 10**9+7
half = mod // 2 + 1
G = [[] for _ in range(N+1)]
for a, b in AB:
    G[a].append(b)
    G[b].append(a)
P = [0] * (N+1)
Size = [0] * (N+1)
def dfs(v):
    siz = 1
    p = P[v]
    for u in G[v]:
        if u != p:
            P[u] = v
            dfs(u)
            siz += Size[u]
    Size[v] = siz
dfs(1)
ans = 0
Prob = [0]
h = 1
for i in range(202020):
    h = h * half % mod
    Prob.append(1-h)
for v, (siz_v, Gv) in enumerate(zip(Size[1:], G[1:]), 1):
    if v == 1:
        ps = []
    else:
        ps = [Prob[N-siz_v]]
    par = P[v]
    for u in Gv:
        if par != u:
            siz_u = Size[u]
            ps.append(Prob[siz_u])
    if len(ps)<=1:
        continue
    cumprod1_ps = [1, 1]
    cumprod2_ps = [1, 1]
    cp = 1
    for p in ps:
        cp = cp * (1-p) % mod
        cumprod1_ps.append(cp)
    cp = 1
    for p in ps[::-1]:
        cp = cp * (1-p) % mod
        cumprod2_ps.append(cp)
    cumprod2_ps.reverse()
    an = 1 - cumprod1_ps[-1]
    for cp1, cp2, p in zip(cumprod1_ps[1:-1], cumprod2_ps[1:-1], ps):
        an -= cp1 * cp2 % mod * p
    ans += an
ans = ans % mod * half % mod
print(ans)

Submission status: Accepted

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

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

Solution code:
import sys
sys.setrecursionlimit(10**9)
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: Accepted

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

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
  now = pows[N-1]-1
  for t in ts:
    # now -= pow(2, t, MOD)-1
    now -= pows[t] - 1
  ans += now
  return res

ans = 0
MOD = 10**9+7
# 高速化1
pows = [1] * (N+1)
for i in range(1, N+1):
  pows[i] = (pows[i - 1] * 2) % MOD

dfs(1)
print((ans * pow(pows[N], MOD-2, MOD)) % MOD)

Submission status: Accepted

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


def dfs(node):
    visited[node] = True
    for child in G[node]:
        if visited[child] == False:
            parent[child] = node
            dfs(child)
    for child in G[node]:
        if child != parent[node]:
            count[node] += count[child]


powers = [1 for i in range(2*10**5+1)]
for i in range(1, 2*10**5+1):
    powers[i] = powers[i-1]*2 % mod

dfs(S)

ans = 0
for i in range(1, N+1):
    if len(G[i]) > 1:
        ans += powers[N-1]
        for x in G[i]:
            if x != parent[i]:
                ans -= powers[count[x]]
        ans -= powers[N-count[i]]
        ans += len(G[i]) - 1
        ans %= mod
D = pow(2, N, mod)
print(ans*pow(D, mod-2, mod) % mod)

Submission status: Accepted

Solution code:
def main():
    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
    # import numpy as np
    # from numba import njit
    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)


    # 再帰を用いないver.
    def dfs(start):
        q = [start]
        # 行きがけ順
        seen = [None]*n
        # 帰りがけ順
        done = [None]*n
        parent = [None]*n
        parent[start] = -1
        d0 = 0
        d1 = n
        while q:
            u = q.pop()
            if u>=0:
                if seen[u] is not None:
                    continue
                seen[u] = d0
                d0 += 1
                q.append(~u)
                for v in ns[u]:
                    if seen[v] is None:
                        q.append(v)
                        parent[v] = u
            else:
                d1 -= 1
                done[~u] = d1
        return seen, done, parent
    seen, done, parent = dfs(0)
    done = [(u,d) for u,d in enumerate(done)]
    done.sort(key = lambda x: -x[1])
    bs = {}
    for u,_ in done:
        val = 1
        p = parent[u]
        for v in ns[u]:
            if v!=p:
                val += bs[u,v]
        bs[p,u] = val

    bs[0,-1] = 0
    for u,_ in reversed(done):
        p = parent[u]
        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

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