Problem:


Score : 600 points

Problem Statement

Given is a tree T with N vertices. The i-th edge connects Vertex A_i and B_i (1 \leq A_i,B_i \leq N).

Now, each vertex is painted black with probability 1/2 and white with probability 1/2, which is chosen independently from other vertices. Then, let S be the smallest subtree (connected subgraph) of T containing all the vertices painted black. (If no vertex is painted black, S is the empty graph.)

Let the holeyness of S be the number of white vertices contained in S. Find the expected holeyness of S.

Since the answer is a rational number, we ask you to print it \bmod 10^9+7, as described in Notes.

Notes

When you print a rational number, first write it as a fraction \frac{y}{x}, where x, y are integers, and x is not divisible by 10^9 + 7
(under the constraints of the problem, such representation is always possible).

Then, you need to print the only integer z between 0 and 10^9 + 6, inclusive, that satisfies xz \equiv y \pmod{10^9 + 7}.

Constraints

2 \leq N \leq 2 \times 10^5

1 \leq A_i,B_i \leq N

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N
A_1 B_1
:
A_{N-1} B_{N-1}

Output

Print the expected holeyness of S, \bmod 10^9+7.

Sample Input 1

3
1 2
2 3

Sample Output 1

125000001

If the vertices 1, 2, 3 are painted black, white, black, respectively, the holeyness of S is 1.

Otherwise, the holeyness is 0, so the expected holeyness is 1/8.

Since 8 \times 125000001 \equiv 1 \pmod{10^9+7}, we should print 125000001.

Sample Input 2

4
1 2
2 3
3 4

Sample Output 2

375000003

The expected holeyness is 3/8.

Since 8 \times 375000003 \equiv 3 \pmod{10^9+7}, we should print 375000003.

Sample Input 3

4
1 2
1 3
1 4

Sample Output 3

250000002

The expected holeyness is 1/4.

Sample Input 4

7
4 7
3 1
2 6
5 2
7 1
2 7

Sample Output 4

570312505



Sample input:
3
1 2
2 3


Sample output:
125000001

Submission status: Time Limit Exceeded

Solution code:
import sys 
sys.setrecursionlimit(10**9)
N = int(input())
G = [[] for _ in range(N)]
mod = 10**9+7
for _ in range(N-1):
    A, B = map(int, input().split())
    G[A-1].append(B-1)
    G[B-1].append(A-1)
cnt = [[] for _ in range(N)]
que = [0]
depth = [-1]*N
depth[0] = 0
while que:
    v = que.pop()
    d = depth[v]
    for nv in G[v]:
        if depth[nv]>=0:
            continue
        depth[nv] = d+1
        que.append(nv)
d_to_i = [[] for _ in range(N)]
for i in range(N):
    d_to_i[depth[i]].append(i)
for d in range(N)[::-1]:
    for v in d_to_i[d]:
        for nv in G[v]:
            if depth[nv]<depth[v]:
                continue
            if cnt[nv]:
                cnt[v].append(sum(cnt[nv])+1)
            else:
                cnt[v].append(1)
for i in range(N):
    res = N-1
    for j in cnt[i]:
        res-=j
    cnt[i].append(res)
ans = 0
for v in range(N):
    if len(cnt[v])<=1:
        continue    
    res = pow(2, N-1, mod)-1
    for a in cnt[v]:
        res-=pow(2, a, mod)-1
    ans+=res
    ans%=mod
inv = pow(2, (mod-2)*N, mod)
print(ans*inv%mod)

Submission status: Time Limit Exceeded

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

mod = 10**9+7
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)

st = [1]
seen = [0] * (N+1)
seen[1] = 1
child = [[] for _ in range(N+1)]
seq = []
while st:
    v = st.pop()
    seq.append(v)
    for u in adj[v]:
        if not seen[u]:
            seen[u] = 1
            st.append(u)
            child[v].append(u)
seq.reverse()

ans = 0
half = pow(2, mod-2, mod)
half_n = pow(half, N-1, mod)
dp = [1] * (N+1)
for v in seq:
    tmp = (1 - half_n)%mod
    tmp2 = 0
    for u in child[v]:
        dp[v] += dp[u]
        tmp2 = (tmp2 + ((1 - pow(half, dp[u], mod))%mod * pow(half, N-dp[u]-1, mod)) % mod) % mod
    if dp[v] < N:
        tmp2 = (tmp2 + ((1 - pow(half, N-dp[v], mod)) % mod * pow(half, dp[v]-1, mod)) % mod) % mod
    if child[v]:
        tmp = (tmp - tmp2) % mod
        ans = (ans + tmp) % mod

print((ans * half)%mod)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def MF(n,d): return ModFraction(n,d)

class ModFraction():
    def __init__(self, n, d):
        self.n = n
        self.d = d

    def __add__(self, x):
        xf = ModFraction.xf(x)
        a = self.n * xf.d % mod
        b = xf.n * self.d % mod
        c = self.d * xf.d % mod
        return ModFraction((a+b) % mod, c)

    def __sub__(self, x):
        xf = ModFraction.xf(x)
        a = self.n * xf.d % mod
        b = -xf.n * self.d % mod
        c = self.d * xf.d % mod
        return ModFraction((a+b) % mod, c)

    def __mul__(self, x):
        xf = ModFraction.xf(x)
        a = self.n * xf.n % mod
        b = self.d * xf.d % mod
        return ModFraction(a, b)

    def __truediv__(self, x):
        xf = ModFraction.xf(x)
        a = self.n * xf.d % mod
        b = self.d * xf.n % mod
        return ModFraction(a, b)

    @classmethod
    def xf(cls, x):
        if isinstance(x, int):
            return ModFraction(x, 1)
        return x

    @classmethod
    def inv(cls, x):
        return pow(x, mod - 2, mod)

    def int(self):
        return self.n * ModFraction.inv(self.d) % mod

    def __str__(self):
        return "{} / {}".format(self.n, self.d)


def main():
    n = I()
    ab = [LI_() for _ in range(n-1)]
    e = collections.defaultdict(list)
    for a,b in ab:
        e[a].append(b)
        e[b].append(a)

    m = {}
    def f(i,p):
        k = (i,p)
        if k in m:
            return m[k]
        r = 1
        for c in e[i]:
            if c == p:
                continue
            r += f(c,i)
        m[k] = r
        return r

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

    r = 0
    for i in range(n):
        cs = []
        for c in e[i]:
            cs.append(f(c,i))
        t = sum(cs)
        for i in range(len(cs)-1):
            t -= cs[i]
            k = pw[cs[i]] - 1
            l = pw[t] - 1
            r += k * l % mod
            r %= mod

    rf = MF(r, pw[n])

    return rf.int()


print(main())

Submission status: Time Limit Exceeded

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

reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__

mod = 10**9+7

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

cnt = [0]*n
def dfs(cur, prev):
    tmp = 1
    for to in G[cur]:
        if to != prev:
            tmp += dfs(to, cur)
    cnt[cur] = tmp
    return tmp

dfs(0, -1)

power = [0]*(n)
powe2_n = pow(2, n, mod)
powe2_n = pow(powe2_n, mod-2, mod)
power[n-1] = powe2_n
for i in reversed(range(n-1)):
    powe2_n *= 2
    powe2_n %= mod
    power[i] = powe2_n
ans = 0
from collections import deque
que = deque()
que.append((0, -1))

while que:
    cur, prev = que.pop()
    if len(G[cur]) == 1:
        if prev == -1:
            que.append((G[cur][0], cur))
        continue

    prob = 1
    prob -= power[n-2]

    for to in G[cur]:
        if to == prev:
            bubun_cnt = n-cnt[cur]
        else:
            que.append((to, cur))
            bubun_cnt = cnt[to]
        tmp = 1-power[bubun_cnt-1]
        tmp *= power[n-1-bubun_cnt-1]
        prob -= tmp
    prob %= mod
    ans += power[0]*prob
    ans %= mod

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def MF(n,d): return ModFraction(n,d)

class ModFraction():
    def __init__(self, n, d):
        self.n = n
        self.d = d

    def __add__(self, x):
        xf = ModFraction.xf(x)
        a = self.n * xf.d % mod
        b = xf.n * self.d % mod
        c = self.d * xf.d % mod
        return ModFraction((a+b) % mod, c)

    def __sub__(self, x):
        xf = ModFraction.xf(x)
        a = self.n * xf.d % mod
        b = -xf.n * self.d % mod
        c = self.d * xf.d % mod
        return ModFraction((a+b) % mod, c)

    def __mul__(self, x):
        xf = ModFraction.xf(x)
        a = self.n * xf.n % mod
        b = self.d * xf.d % mod
        return ModFraction(a, b)

    def __truediv__(self, x):
        xf = ModFraction.xf(x)
        a = self.n * xf.d % mod
        b = self.d * xf.n % mod
        return ModFraction(a, b)

    @classmethod
    def xf(cls, x):
        if isinstance(x, int):
            return ModFraction(x, 1)
        return x

    @classmethod
    def inv(cls, x):
        return pow(x, mod - 2, mod)

    def int(self):
        return self.n * ModFraction.inv(self.d) % mod

    def __str__(self):
        return "{} / {}".format(self.n, self.d)


def main():
    n = I()
    ab = [LI_() for _ in range(n-1)]
    e = collections.defaultdict(list)
    for a,b in ab:
        e[a].append(b)
        e[b].append(a)

    m = {}
    def f(i,p):
        k = (i,p)
        if k in m:
            return m[k]
        r = 1
        for c in e[i]:
            if c == p:
                continue
            r += f(c,i)
        m[k] = r
        return r

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

    r = 0
    for i in range(n):
        cs = []
        for c in e[i]:
            cs.append(f(c,i))
        if len(cs) < 2:
            continue
        t = sum(cs)
        for i in range(len(cs)-1):
            t -= cs[i]
            k = pw[cs[i]] - 1
            l = pw[t] - 1
            r += k * l % mod
            r %= mod

    rf = MF(r, pw[n])

    return rf.int()


print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys 
sys.setrecursionlimit(10**9)
N = int(input())
G = [[] for _ in range(N)]
mod = 10**9+7
for _ in range(N-1):
    A, B = map(int, input().split())
    G[A-1].append(B-1)
    G[B-1].append(A-1)
cnt = [[] for _ in range(N)]
def dfs(p, v, n):
    s = 0
    for nv in G[v]:
        if nv == p:
            continue
        res = dfs(v, nv, n+1)
        cnt[v].append(res)
        s+=res
    cnt[v].append(N-s-1)
    return s+1
dfs(-1, 0, 0) 

ans = 0
for v in range(N):
    if len(cnt[v])<=1:
        continue    
    res = pow(2, N-1, mod)-1
    for a in cnt[v]:
        res-=pow(2, a, mod)-1
    ans+=res
    ans%=mod
inv = pow(2, (mod-2)*N, mod)
print(ans*inv%mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(2*10**5)
mod=10**9+7
N=int(input())
G=[[] for i in range(N)]
for i in range(N-1):
    A,B=map(int,input().split())
    G[A-1].append(B-1)
    G[B-1].append(A-1)
Child=[[] for i in range(N)]
Parents=[-1 for i in range(N)]
reached=[0 for i in range(N)]
q=deque([])
q.append(0)
while(len(q)>0):
    r=q.popleft()
    reached[r]=1
    for p in G[r]:
        if reached[p]==1:
            continue
        Child[r].append(p)
        Parents[p]=r
        q.append(p)
#print(Child)
#print(Parents)
Childnum=[-1 for i in range(N)]
def dp(i):
    if Childnum[i]!=-1:
        return Childnum[i]
    if len(Child[i])==0:
        Childnum[i]=0
        return 0
    res=0
    for j in Child[i]:
        res+=dp(j)+1
    Childnum[i]=res
    return res
dp(0)
#print(Childnum)
def inv(x):
    return pow(x,mod-2,mod)
ans=0
for r in range(N):
    anstmp=1
    anstmp-=inv(pow(2,N-1,mod))
    anstmp%=mod
    tmp=0
    for p in Child[r]:
        ai=Childnum[p]+1
        tmp+=ai
        k1=(1-inv(pow(2,ai,mod)))%mod
        k2=inv(pow(2,N-1-ai,mod))
        #print(r,p,(k1*k2)%mod)
        anstmp-=(k1*k2)%mod
        anstmp%=mod
    ai=N-1-tmp
    k1=(1-inv(pow(2,ai,mod)))%mod
    k2=inv(pow(2,N-1-ai,mod))
    anstmp-=(k1*k2)%mod
    #print(r,-1,(k1*k2)%mod)
    anstmp%=mod
    ans+=anstmp
    #print(anstmp)
    ans%=mod
print((ans*inv(2))%mod)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def MF(n,d): return ModFraction(n,d)

class ModFraction():
    def __init__(self, n, d):
        self.n = n
        self.d = d

    def __add__(self, x):
        xf = ModFraction.xf(x)
        a = self.n * xf.d % mod
        b = xf.n * self.d % mod
        c = self.d * xf.d % mod
        return ModFraction((a+b) % mod, c)

    def __sub__(self, x):
        xf = ModFraction.xf(x)
        a = self.n * xf.d % mod
        b = -xf.n * self.d % mod
        c = self.d * xf.d % mod
        return ModFraction((a+b) % mod, c)

    def __mul__(self, x):
        xf = ModFraction.xf(x)
        a = self.n * xf.n % mod
        b = self.d * xf.d % mod
        return ModFraction(a, b)

    def __truediv__(self, x):
        xf = ModFraction.xf(x)
        a = self.n * xf.d % mod
        b = self.d * xf.n % mod
        return ModFraction(a, b)

    @classmethod
    def xf(cls, x):
        if isinstance(x, int):
            return ModFraction(x, 1)
        return x

    @classmethod
    def inv(cls, x):
        return pow(x, mod - 2, mod)

    def int(self):
        return self.n * ModFraction.inv(self.d) % mod

    def __str__(self):
        return "{} / {}".format(self.n, self.d)


def main():
    n = I()
    ab = [LI_() for _ in range(n-1)]
    e = collections.defaultdict(list)
    for a,b in ab:
        e[a].append(b)
        e[b].append(a)

    m = {}
    def f(i,p):
        k = (i,p)
        if k in m:
            return m[k]
        r = 1
        for c in e[i]:
            if c == p:
                continue
            r += f(c,i)
        m[k] = r
        return r

    r = 0
    for i in range(n):
        cs = []
        for c in e[i]:
            cs.append(f(c,i))
        if len(cs) < 2:
            continue
        t = sum(cs)
        for i in range(len(cs)-1):
            t -= cs[i]
            k = pow(2, cs[i], mod) - 1
            l = pow(2, t, mod) - 1
            r += k * l
            r %= mod

    rf = MF(r, pow(2,n,mod))

    return rf.int()


print(main())

Submission status: Accepted

Solution code:
# 75

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):
    # calc : (a**(-1)) %MOD
    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 += (1 - (1/2)**num_l[i]) * (1 - (1/2)**(N-num_l[i]))
    # ans += 1 - (1/2)**N  # 辺の期待値→頂点の期待値に変換(空集合以外は+1される)
    # ans -= N/2  # 黒点の期待値を引く
    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()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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