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

Solution (Python):


import sys
sys.setrecursionlimit(10**8)

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


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


def modinv(a):
    
    return pow(a, MOD-2, MOD)


def solve():
    dfs(0)
    pow_l = [None]*(N+1)
    pow_l[0] = 1
    for i in range(1, N+1):
        pow_l[i] = (pow_l[i-1] * 2) % MOD

    ans = 0
    
    
    
    
    for i in range(1, N):
        ans = (ans + (pow_l[num_l[i]]-1) *
               (pow_l[N-num_l[i]]-1) % MOD) % MOD
    ans = (ans + (pow_l[N] - 1) - (N * pow_l[N-1]) % MOD) % MOD
    y = ans
    x = pow(2, N, MOD)

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

    print(z)


solve()

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

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

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

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

from collections import deque, defaultdict


from collections import Counter

from itertools import accumulate,combinations,permutations,product

from heapq import heapify,heappop,heappush

from functools import reduce,lru_cache

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("
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= 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=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):
        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()
            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
    

    N = int(input())
    
    
    
    

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

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


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

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

from collections import deque, defaultdict


from collections import Counter

from itertools import accumulate,combinations,permutations,product

from heapq import heapify,heappop,heappush

from functools import reduce,lru_cache

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("
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= 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=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):
        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()
            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
    

    N = int(input())
    
    
    
    

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

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


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

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

from collections import deque, defaultdict


from collections import Counter

from itertools import accumulate,combinations,permutations,product

from heapq import heapify,heappop,heappush

from functools import reduce,lru_cache

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("
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= 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=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):
        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()
            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
    

    N = int(input())
    
    
    
    

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

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

Solution (Python):
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)
        
    
    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
    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
        temp=POW[N-1]
        temp-=1
        
        for s in L[v]:
            temp-=POW[s]-1
            temp%=mod
            
        
        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:
                
                if len(L[nv])>=deg[nv]-1:
                    q.put(nv)
                    looked[nv]=1
                
                
    
    
    y=sum(ans)
    x=POW[N]
    
    res=(y*pow(x,mod-2,mod))%mod
    print(res)
    
        
    
        
    
    

main()

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


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)

ans = 0

def dfs(v,p): 
  global ans 
  res = 1 
  ts = [] 
  for u in G[v]:
    if u == p:
      continue
    t = dfs(u,v) 
    res += t
    ts.append(t)
  if p != -1: 
    ts.append(N-res)
  now = beki[N-1] - 1 
  for x in ts:
    now -= beki[x] - 1 
  ans = (ans+now)%MOD
  return res 

dfs(0,-1)
ALL = pow(2,N,MOD)

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

Solution (Python):
import sys
sys.setrecursionlimit(500000)
input = sys.stdin.readline
N = int(input()); MOD=pow(10,9)+7
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)

ans = 0

def dfs(v,p): 
  global ans 
  res = 1 
  ts = [] 
  for u in G[v]:
    if u == p:
      continue
    t = dfs(u,v) 
    res += t
    ts.append(t)
  if p != -1: 
    ts.append(N-res)
  now = pow(2,N-1,MOD) - 1 
  for x in ts:
    now -= pow(2,x,MOD) - 1 
  ans = (ans+now)%MOD
  return res 

dfs(0,-1)
ALL = pow(2,N,MOD)

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

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

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

Solution (Python):

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)

Solution (Python):


from collections import deque
import sys
input = sys.stdin.readline

def dfs():
    stk1 = deque([0])
    stk2 = deque([])
    while stk1:
        v = stk1.pop()
        visited[v] = True
        stk2.append(v)
        for i in range(len(AL[v][CHILDREN])):
            u = AL[v][CHILDREN][i]
            if visited[u]:
                AL[v][CHILDREN][i] = None
                continue
            stk1.append(u)

    for i in range(n - 1, -1, -1):
        v = stk2[i]
        for u in AL[v][CHILDREN]:
            if u is None:  continue
            AL[v][SIZE] += AL[u][SIZE]

def anaaki(v):
    ret = pow(2, n - 1, p) - 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

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

Solution (Python):

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)

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

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
G = [[] for _ in range(n)]
for _ in range(n - 1):
    a, b = LI()
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]


par = [-1] * n
cnt = [0] * n


def f(u):
    ret = 1
    for v in G[u]:
        if v == par[u]:
            continue
        par[v] = u
        ret += f(v)
    cnt[u] = ret
    return ret

f(0)
pow2 = [1] * (n + 1)
for i in range(1, n + 1):
    pow2[i] = pow2[i - 1] * 2 % mod

q = deque([0])
ans = 0
while q:
    u = q.pop()
    ret = pow2[n - 1] - 1
    for v in G[u]:
        if v == par[u]:
            continue
        ret -= pow2[cnt[v]] - 1
        q += [v]
    ret -= pow2[n - cnt[u]] - 1
    ans = (ans + ret) % mod

print(ans * pow(pow2[n], mod - 2, mod) % mod)

Solution (Python):
import sys
sys.setrecursionlimit(10**6)
mod = 10**9+7
p2 = [1]*(3*10**5)
for n in range(3*10**5-1):
    p2[n+1] = p2[n]*2%mod

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

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

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

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

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

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

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

    
    
    
    
    
    
    
    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  
        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:
            
            continue
        cnt_not = 0  
        for dir_node in adj[node]:
            
            cnt_not += pow_2[node_num[(node, dir_node)]]
        cnt_not -= len(adj[node]) - 1  
        numer += pow_2[N - 1] - cnt_not  

    
    denom = pow_2[N]

    
    print(numer * mod_inv(denom, MOD) % MOD)


if __name__ == '__main__':
    main()