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

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

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

dfs()
solve()

Submission status: Time Limit Exceeded

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

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


#頂点xから伸びる部分木に含まれる頂点の個数のリストを返す
def get_sub_tree_node_nums(x):
    ret=[]
    for s in E[x]:
        if parent[x]!=s:
            ret.append(dp[s])
    if x!=root:
        ret.append(N-dp[x])
    return ret

def solve():
    ans=0
    inv2=pow(2,MOD-2,MOD)
    #p0=すべての部分木に黒頂点が1つも含まれない確率
    p0=pow(1<<(N-1),MOD-2,MOD)
    for i in range(N):
        p=0
        subnodes = get_sub_tree_node_nums(i)
        if len(subnodes)>=2:
            #p0*(p1-1)=どれか1つの各部分木に黒頂点が1つ以上含まれる確率
            p1=1
            for s in subnodes:
                p1+=(1<<s)-1
                p1%=MOD
            p=1-(p0*p1)
            p%=MOD
            #頂点iが白の確率
            p=p*inv2%MOD
        ans+=p
        ans%=MOD
    print(ans)

dfs()
solve()

Submission status: Time Limit Exceeded

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

#頂点xから伸びる部分木に含まれる頂点の個数のリストを返す
def get_sub_tree_node_nums(x):
    ret=[]
    used=[False]*N
    used[x]=True
    for s in E[x]:
        n=1
        stack=[s]
        used[s]=True
        while stack:
            node=stack.pop()
            for ss in E[node]:
                if not used[ss]:
                    stack.append(ss)
                    n+=1
                    used[ss]=True
        ret.append(n)
    return ret

def solve():
    ans=0
    inv2=pow(2,MOD-2,MOD)
    #p0=すべての部分木に黒頂点が1つも含まれない確率
    p0=pow(1<<(N-1),MOD-2,MOD)
    for i in range(N):
        p=0
        subnodes = get_sub_tree_node_nums(i)
        if len(subnodes)>=2:
            #p0*(p1-1)=どれか1つの各部分木に黒頂点が1つ以上含まれる確率
            p1=1
            for s in subnodes:
                p1+=(1<<s)-1
                p1%=MOD
            p=1-(p0*p1)
            p%=MOD
            #頂点iが白の確率
            p=p*inv2%MOD
        ans+=p
        ans%=MOD
    print(ans)

solve()

Submission status: Time Limit Exceeded

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

#頂点xから伸びる部分木に含まれる頂点の個数のリストを返す
def get_sub_tree_node_nums(x):
    ret=[]
    used=[False]*N
    used[x]=True
    for s in E[x]:
        n=1
        stack=[s]
        used[s]=True
        while stack:
            node=stack.pop()
            for ss in E[node]:
                if not used[ss]:
                    stack.append(ss)
                    n+=1
                    used[ss]=True
        ret.append(n)
    return ret

n2=[0]*(N+1)
inv2=[0]*(N+1)
def calc_inv2():
    n2[0]=inv2[0]=1
    for i in range(1,len(inv2)):
        n2[i]=n2[i-1]*2%MOD
        inv2[i]=pow(1<<i,MOD-2,MOD)

def solve():
    ans=0
    for i in range(N):
        p=0
        subnodes = get_sub_tree_node_nums(i)
        if len(subnodes)>=2:
            #p0=すべての部分木に黒頂点が1つも含まれない確率
            p0=inv2[N-1]
            #p0*(p1-1)=どれか1つの各部分木に黒頂点が1つ以上含まれる確率
            p1=1
            for s in subnodes:
                p1+=n2[s]-1
                p1%=MOD
            p=1-(p0*p1)
            p%=MOD
            #頂点iが白の確率
            p=p*inv2[1]%MOD
        ans+=p
        ans%=MOD
    print(ans)
            
calc_inv2()
solve()

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]

sys.setrecursionlimit(10**6)
MOD = 10**9+7

n = int(input())

pows = [1]
for _ in range(n):
	pows.append((pows[-1] * 500000004) % MOD)

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

ans = 0
def dfs(x, p):
	global ans
	cnt = 1
	tmp = 1 - pows[n-1]
	for v in adj[x]:
		if v == p:
			continue
		w = dfs(v, x)
		tmp -= pows[n-1-w] - pows[n-1]
		cnt += w
	if n > cnt:
		tmp -= pows[cnt-1] - pows[n-1]
	tmp = (tmp * 500000004) % MOD
	ans = (ans + tmp) % MOD

	return cnt

dfs(0, -1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]

sys.setrecursionlimit(10**6)
MOD = 10**9+7

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

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

ans = 0
def dfs(x, p):
	global branches, ans
	cnt = 1
	tmp = 1 - pow(500000004, n-1, MOD)
	for v in adj[x]:
		if v == p:
			continue
		w = dfs(v, x)
		tmp -= pow(500000004, n-1-w, MOD) - pow(500000004, n-1, MOD)
		cnt += w
	if n > cnt:
		tmp -= pow(500000004, cnt-1, MOD) - pow(500000004, n-1, MOD)
	tmp = (tmp * 500000004) % MOD
	ans = (ans + tmp) % MOD

	return cnt

dfs(0, -1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
MOD = 10**9+7

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

ans = 0
def dfs(x, p):
	global ans
	cnt = 1
	tmp = 1 - pow(500000004, n-1, MOD)
	for v in adj[x]:
		if v == p:
			continue
		w = dfs(v, x)
		tmp -= pow(500000004, n-1-w, MOD) - pow(500000004, n-1, MOD)
		cnt += w
	if n > cnt:
		tmp -= pow(500000004, cnt-1, MOD) - pow(500000004, n-1, MOD)
	tmp = (tmp * 500000004) % MOD
	ans = (ans + tmp) % MOD

	return cnt

dfs(0, -1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
MOD = 10**9+7

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

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

def dfs(x, p):
	global branches
	cnt = 1
	for v in adj[x]:
		if v == p:
			continue
		w = dfs(v, x)
		branches[x].append(w)
		cnt += w
	if n > cnt:
		branches[x].append(n-cnt)
	return cnt

dfs(0, -1)

ans = 0
for b in branches:
	if len(b) == 1:
		continue
	tmp = 1 - pow(500000004, n-1, MOD)
	for c in b:
		tmp -= pow(500000004, n-1-c, MOD) - pow(500000004, n-1, MOD)
	tmp = (tmp * 500000004) % MOD
	ans = (ans + tmp) % MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
MOD = 10**9+7

def pow2(p):
	return pow(500000004, p, MOD)

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

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

def dfs(x, p):
	global branches
	cnt = 1
	for v in adj[x]:
		if v == p:
			continue
		w = dfs(v, x)
		branches[x].append(w)
		cnt += w
	if n > cnt:
		branches[x].append(n-cnt)
	return cnt

dfs(0, -1)

ans = 0
for b in branches:
	if len(b) == 1:
		continue
	tmp = 1 - pow2(n-1)
	for c in b:
		tmp -= pow2(n-1-c) - pow2(n-1)
	tmp = (tmp * 500000004) % MOD
	ans = (ans + tmp) % MOD

print(ans)

Submission status: Time Limit Exceeded

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

mod = 10**9+7

n = int(input())
g = [[] for _ in range(n)]

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

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

depth = [-1]*n
ko_all = [0 for _ in range(n)]
ko_only =[0 for _ in range(n)]

def dfs(v,d):
    depth[v] = d
    for w in g[v]:
        if depth[w] == -1:
            dfs(w,d+1)
            ko_all[v] += ko_all[w]+1
            ko_only[v] += pow2[ko_all[w]+1]-1

dfs(0,0)

cnt = 0

for i in range(n):
    tmp = pow2[n-1]-1-(pow2[n-1-ko_all[i]]-1) - ko_only[i]
    tmp %=mod
    cnt += tmp
    cnt %= mod

def inv(a,mod):
    r = [1,0,a]
    w = [0,1,mod]
    while w[2]!=1:
        q = r[2]//w[2]
        r_new = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = w
        w = r_new
    x,y = w[0],w[1]    # a*x+y*mod = 1
    return (mod+x%mod)%mod

print(inv(pow2[n],mod)*cnt %mod)

Submission status: Time Limit Exceeded

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

mod = 10**9+7

n = int(input())
g = [[] for _ in range(n)]

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

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

depth = [-1]*n
ko = [[] for _ in range(n)]
ko_all = [0 for _ in range(n)]


def dfs(v,d):
    depth[v] = d
    for w in g[v]:
        if depth[w] == -1:
            ko[v].append(w)
            dfs(w,d+1)
            ko_all[v] += ko_all[w]+1

dfs(0,0)

cnt = 0

for i in range(n):
    tmp = pow2[n-1]-1-(pow2[n-1-ko_all[i]]-1)
    tmp %=mod
    for w in ko[i]:
        tmp -= pow2[ko_all[w]+1]-1
        tmp %= mod
    cnt += tmp
    cnt %= mod


def inv(a,mod):
    r = [1,0,a]
    w = [0,1,mod]
    while w[2]!=1:
        q = r[2]//w[2]
        r_new = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = w
        w = r_new
    x,y = w[0],w[1]    # a*x+y*mod = 1
    return (mod+x%mod)%mod

print(inv(pow2[n],mod)*cnt %mod)

Submission status: Time Limit Exceeded

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

mod = 10**9+7

n = int(input())
g = [[] for _ in range(n)]

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

depth = [-1]*n
ko = [[] for _ in range(n)]
ko_all = [0 for _ in range(n)]


def dfs(v,d):
    depth[v] = d
    for w in g[v]:
        if depth[w] == -1:
            ko[v].append(w)
            dfs(w,d+1)
            ko_all[v] += ko_all[w]+1

dfs(0,0)

cnt = 0

for i in range(n):
    tmp = 2**(n-1)-1-(2**(n-1-ko_all[i])-1)
    tmp %=mod
    for w in ko[i]:
        tmp -= 2**(ko_all[w]+1)-1
        tmp %= mod
    cnt += tmp
    cnt %= mod


def inv(a,mod):
    r = [1,0,a]
    w = [0,1,mod]
    while w[2]!=1:
        q = r[2]//w[2]
        r_new = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = w
        w = r_new
    x,y = w[0],w[1]    # a*x+y*mod = 1
    return (mod+x%mod)%mod

print(inv(2**n,mod)*cnt %mod)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(200001)


def dfs1(v, p):
    global parent, subtree_count, links
    parent[v] = p
    stc = subtree_count[v]
    cnt = 1
    for u in links[v]:
        if u == p:
            continue
        result = dfs1(u, v)
        stc[u] = result
        cnt += result
    return cnt


def dfs2(root):
    global parent, subtree_count

    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
parent = [-1] * n
subtree_count = [{} for _ in range(n)]  # 根がrootの時の、vの子の各部分木のノード数
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)
dfs1(root, -1)
# print(parent)
# print(subtree_count)
ans = dfs2(root)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(200001)


def dfs1(v, p):
    global parent, subtree_count, links
    parent[v] = p
    stc = subtree_count[v]
    cnt = 1
    for u in links[v]:
        if u == p:
            continue
        result = dfs1(u, v)
        stc[u] = result
        cnt += result
    return cnt


def dfs2(v, pc):
    # pc: vを根とした時の、parent方面の部分木のノード数
    global ans, parent, subtree_count

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

    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():
        dfs2(u, ct - stc + 1)

    if cl == 1:
        return

    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


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
parent = [-1] * n
subtree_count = [{} for _ in range(n)]  # 根がrootの時の、vの子の各部分木のノード数
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)
ans = 0
dfs1(root, -1)
# print(parent)
# print(subtree_count)
dfs2(root, 0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(200001)


def dfs1(v, p):
    parent[v] = p
    stc = subtree_count[v]
    cnt = 1
    for u in links[v]:
        if u == p:
            continue
        result = dfs1(u, v)
        stc[u] = result
        cnt += result
    return cnt


def dfs2(v, pc):
    # pc: vを根とした時の、parent方面の部分木のノード数
    global ans

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

    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():
        dfs2(u, ct - stc + 1)

    if cl == 1:
        return

    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


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
parent = [-1] * n
subtree_count = [{} for _ in range(n)]  # 根がrootの時の、vの子の各部分木のノード数
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)
ans = 0
dfs1(root, -1)
# print(parent)
# print(subtree_count)
dfs2(root, 0)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import accumulate

sys.setrecursionlimit(10 ** 5)


def dfs1(v, p):
    parent[v] = p
    stc = subtree_count[v]
    cnt = 1
    for u in links[v]:
        if u == p:
            continue
        result = dfs1(u, v)
        stc[u] = result
        cnt += result
    return cnt


def dfs2(v, pc):
    # pc: vを根とした時の、parent方面の部分木のノード数
    global ans

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

    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():
        dfs2(u, ct - stc + 1)

    if cl == 1:
        return

    prob_fwd = [0] + list(accumulate(st_counts[:-1]))
    prob_bwd = [0] + list(accumulate(st_counts[-1:0:-1]))
    prob_bwd.reverse()
    tmp = 0
    for pf, pb in zip(prob_fwd, prob_bwd):
        tmp = (tmp + d2s[pf + pb]) % MOD
    tmp = (tmp - d2s[ct] * (cl - 1)) % MOD
    ans = (ans + (1 - tmp) * d2) % MOD


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
parent = [-1] * n
subtree_count = [{} for _ in range(n)]  # 根がrootの時の、vの子の各部分木のノード数
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)
ans = 0
dfs1(root, -1)
# print(parent)
# print(subtree_count)
dfs2(root, 0)
print(ans)

Submission status: Time Limit Exceeded

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
inv2 = (mod + 1) // 2
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-pow(inv2, N - A[i], mod)) * pow(2, N - A[i], mod)
    for j in X[i]:
        s = (s * pow(inv2, A[j], mod)) % mod
        t = (t + (1-pow(inv2, A[j], mod)) * pow(2, A[j], mod)) % mod
    ans = (ans + 1 - s * t) % mod

print(ans * inv2 % mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
from collections import defaultdict
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)

def dfs(i,j):
    if d[(i,j)]!=-1:
        return d[(i,j)]
    res = 1
    for k in g[j]:
        if k==i:
            continue
        res += dfs(j,k)
    d[(i,j)] = res
    return res

for i in range(N):
    if len(g[i])==1:
        dfs(i,g[i][0])
        break

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: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
from collections import defaultdict
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)

def dfs(i,j):
    if d[(i,j)]!=-1:
        return d[(i,j)]
    res = 1
    for k in g[j]:
        if k==i:
            continue
        res += dfs(j,k)
    d[(i,j)] = res
    return res
dfs(a,b)
dfs(b,a)

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: Time Limit Exceeded

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

stack = [0]
depth = [-1]*n
depth[0] = 0
while stack:
    v = stack.pop()
    d = depth[v]
    for nv in G[v]:
        if depth[nv] >= 0:continue
        depth[nv] = depth[v] + 1
        stack.append(nv)

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

for i in range(n):
    d_to_i[depth[i]].append(i)

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

for d in range(n-1,-1,-1):
    for v in d_to_i[d]:
        for nv in G[v]:
            if depth[nv] < depth[v]:continue
            if data[nv]:
                data[v].append(n-data[nv][-1])
        if data[v]:
            data[v].append(n-1-sum(data[v]))
        else:
            data[v].append(n-1)

ans = 0
two = [1]
for i in range(n):
    two.append(two[-1]*2%mod)
for i in range(n):
    now = two[n-1]-1
    for x in data[i]:
        now -= two[x]-1
        now %= mod
    ans += now

#print(ans)

x = two[n]
x = pow(x,mod-2,mod)
print(ans*x%mod)

Submission status: Time Limit Exceeded

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

stack = [0]
depth = [-1]*n
depth[0] = 0
while stack:
    v = stack.pop()
    d = depth[v]
    for nv in G[v]:
        if depth[nv] >= 0:continue
        depth[nv] = depth[v] + 1
        stack.append(nv)

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

for i in range(n):
    d_to_i[depth[i]].append(i)

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

for d in range(n-1,-1,-1):
    for v in d_to_i[d]:
        for nv in G[v]:
            if depth[nv] < depth[v]:continue
            if data[nv]:
                data[v].append(n-data[nv][-1])
        if data[v]:
            data[v].append(n-1-sum(data[v]))
        else:
            data[v].append(n-1)

ans = 0
for i in range(n):
    now = pow(2,n-1,mod)-1
    for x in data[i]:
        now -= pow(2,x,mod)-1
        now %= mod
    ans += now

#print(ans)

x = pow(2,n,mod)
x = pow(x,mod-2,mod)
print(ans*x%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(3*10**5)

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

mod = 10**9 + 7

data = [[] for i in range(n)]

def solve(pre,now):
    # output [部分木の頂点数,親の側の頂点数]
    data_now = []
    for nex in G[now]:
        if nex == pre:continue
        data_nex = solve(now,nex)
        data_now.append(n-data_nex[-1])

    data_now.append(n-1-sum(data_now))
    data[now] = data_now
    return data_now

solve(-1,0)

ans = 0
for i in range(n):
    now = pow(2,n-1,mod)-1

    for x in data[i]:

        now -= pow(2,x,mod)-1
        now %= mod
    ans += now

#print(ans)

x = pow(2,n,mod)
x = pow(x,mod-2,mod)
print(ans*x%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(3*10**5)

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

mod = 10**9 + 7

data = [[] for i in range(n)]

def solve(pre,now):
    # output [部分木の頂点数,親の側の頂点数]
    data_now = []
    for nex in G[now]:
        if nex == pre:continue
        data_nex = solve(now,nex)
        data_now.append(sum(data_nex[:-1])+1)
    if len(data_now) == 0:
        data_now.append(0)

    data_now.append(n-1-sum(data_now))
    data[now] = data_now
    return data_now

solve(-1,0)

ans = 0
for i in range(n):
    now = pow(2,n-1,mod)-1

    for x in data[i]:

        now -= pow(2,x,mod)-1
        now %= mod
    ans += now

#print(ans)

x = pow(2,n,mod)
x = pow(x,mod-2,mod)
print(ans*x%mod)

Submission status: Time Limit Exceeded

Solution code:
import os
import sys
from collections import defaultdict

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

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

# 頂点ごとに穴あきになる確率を調べる
# 全パターン数 2^N を掛けて合計すればいい
# 自分をrootにしたときに黒をもつ子が2つ以上ある

children_counts = [defaultdict(int) for _ in range(N)]
hist = []
root = 0
stack = [(root, None)]
while stack:
    v, parent = stack.pop()
    hist.append((v, parent))
    for u in graph[v]:
        if u == parent:
            continue
        stack.append((u, v))
hist.reverse()
dfs = [0] * N
for v, parent in hist:
    ret = 0
    for u in graph[v]:
        if u == parent:
            continue
        cnt = dfs[u]
        children_counts[v][cnt] += 1
        ret += cnt
    ret += 1
    if v != root:
        children_counts[v][N - ret] += 1
    dfs[v] = ret
# print(dfs)

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

# 穴あきにならない期待値
E = [0] * N
for v, counts in enumerate(children_counts):
    if len(graph[v]) == 1:
        # 端っこ
        E[v] = pow2[N]
        continue
    # 黒のときはどう選んでもダメ
    e = pow2[N - 1]
    # 1つだけ黒が含まれる確率は
    for children, cnt in counts.items():
        # ほかが全部白なのは1パターン
        # 1つ以上黒が含まれるのは
        curo = pow2[children] - 1
        e += (curo * cnt) % MOD
    # 自分の色は白
    # 全部白のパターン加算
    E[v] = (e + 1) % MOD
# 穴あきになる期待値
E = [(pow2[N] - e) % MOD for e in E]
ans = div_mod(sum(E), pow2[N], MOD)
print(ans)

Submission status: Time Limit Exceeded

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

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

# 頂点ごとに穴あきになる確率を調べる
# 全パターン数 2^N を掛けて合計すればいい
# 自分をrootにしたときに黒をもつ子が2つ以上ある

children_counts = [None for _ in range(N)]
parents = [None] * N


def dfs(v, parent=None):
    parents[v] = parent
    counts = {}
    ret = 0
    for u in graph[v]:
        if u == parent:
            continue
        cnt = dfs(u, v)
        if cnt in counts:
            counts[cnt] += 1
        else:
            counts[cnt] = 1
        ret += cnt
    ret += 1
    if v != root:
        if N - ret in counts:
            counts[N - ret] += 1
        else:
            counts[N - ret] = 1
    children_counts[v] = counts
    return ret


root = 0
dfs(root)

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

# 穴あきにならない期待値
E = [0] * N
for v, counts in enumerate(children_counts):
    if len(graph[v]) == 1:
        # 端っこ
        E[v] = pow2[N]
        continue
    # 黒のときはどう選んでもダメ
    e = pow2[N - 1]
    # 1つだけ黒が含まれる確率は
    for children, cnt in counts.items():
        # ほかが全部白なのは1パターン
        # 1つ以上黒が含まれるのは
        curo = pow2[children] - 1
        e += (curo * cnt) % MOD
    # 自分の色は白
    # 全部白のパターン加算
    E[v] = (e + 1) % MOD
# 穴あきになる期待値
E = [(pow2[N] - e) % MOD for e in E]
ans = div_mod(sum(E), pow2[N], MOD)
print(ans)

Submission status: Time Limit Exceeded

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

#print(Child)
#print(Parents)
#print(G)
reached=[0 for i in range(N)]
Childnum=[0 for i in range(N)]
def dp(i):
    if reached[i]==1:
        return Childnum[i]
    reached[i]=1
    res=0
    for j in G[i]:
        if reached[j]==1:
            continue
        Child[i].append(j)
        res+=dp(j)+1
    Childnum[i]=res
    return res
dp(0)
#print(Child)
#print(Childnum)
def inv(x):
    return pow(x,mod-2,mod)
inv2=[inv(pow(2,i,mod)) for i in range(N+1)]
ans=(N*(1-inv(pow(2,N-1,mod))))%mod
for r in range(N):
    tmp=0
    for p in Child[r]:
        ai=Childnum[p]+1
        tmp+=ai
        k1=(1-inv2[ai])%mod
        k2=inv2[N-1-ai]
        #print(r,p,(k1*k2)%mod)
        ans-=(k1*k2)%mod
        ans%=mod
    ai=N-1-tmp
    k1=(1-inv2[ai])%mod
    k2=inv2[N-1-ai]
    ans-=(k1*k2)%mod
    #print(r,-1,(k1*k2)%mod)
    ans%=mod
print((ans*inv(2))%mod)