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:
#!/usr/bin/env python3

import sys
sys.setrecursionlimit(300000)

MOD = 1000000007  # type: int

def calc_fraction_mod(numerator, denominator):
    '''
        returns numerator / denominator (mod MOD)
    '''
    inv = pow(denominator, MOD - 2, MOD)
    return numerator * inv % MOD

def solve(N: int, A: "List[int]", B: "List[int]"):
    conns = [[] for _ in range(N)]
    for i in range(N - 1):
        conns[A[i] - 1].append(B[i] - 1)
        conns[B[i] - 1].append(A[i] - 1)

    num = [0]
    visited = [False] * N
    def dfs(idx):
        visited[idx] = True
        children = 0
        subs = []
        for c in conns[idx]:
            if visited[c]:
                continue
            sub = dfs(c)
            children += sub
            subs.append(sub)
        subs.append(N - children - 1)
        tmp = pow(2, N - 1, MOD)
        tmp -= 1 # all white
        for sub in subs:
            tmp -= pow(2, sub, MOD) - 1
        num[0] += tmp
        return children + 1
    dfs(0)

    deno = pow(2, N, MOD)
    num = num[0]
    ret = calc_fraction_mod(num, deno)
    print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int()] * (N - 1)  # type: "List[int]"
    B = [int()] * (N - 1)  # type: "List[int]"
    for i in range(N - 1):
        A[i] = int(next(tokens))
        B[i] = int(next(tokens))
    solve(N, A, B)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


MOD = 1000000007

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)


seen = [False] * N

numer = 0
pow2 = [1] * (N + 1)
for i in range(N):
    pow2[i + 1] = pow2[i] * 2 % MOD

def dfs1(v):
    global numer
    seen[v] = True
    nodes = []
    childs = 0
    for nv in G[v]:
        if not seen[nv]:
            nodes.append(dfs1(nv) + 1)
            childs += nodes[-1]
    if v != 0:
        nodes.append(N - childs - 1)
    if len(nodes) > 1:
        this_numer = pow2[N - 1] - (sum(pow2[n] - 1 for n in nodes) + 1)
        numer = (numer + this_numer) % MOD
    return childs


dfs1(0)

denom = pow2[N]
ans = numer * pow(denom, MOD - 2, MOD) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


MOD = 1000000007

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)

childs = [0] * N
seen = [False] * N


def dfs1(v):
    seen[v] = True
    c = 0
    for nv in G[v]:
        if not seen[nv]:
            dfs1(nv)
            c += childs[nv] + 1
    childs[v] = c
    return


dfs1(0)

numer = 0
seen = [False] * N

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


def dfs2(v):
    global numer
    seen[v] = True
    nodes = []
    for nv in G[v]:
        if seen[nv]:
            nodes.append(N - childs[v] - 1)
        else:
            nodes.append(childs[nv] + 1)
    if len(nodes) > 1:
        this_numer = pow2[N - 1] - (sum(pow2[n] - 1 for n in nodes) + 1)
        numer = (numer + this_numer) % MOD
    for nv in G[v]:
        if not seen[nv]:
            dfs2(nv)
    return


dfs2(0)
denom = pow2[N]
ans = numer * pow(denom, MOD - 2, MOD) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit
from functools import lru_cache

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


MOD = 1000000007

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)

childs = [0] * N
seen = [False] * N


def dfs1(v):
    seen[v] = True
    c = 0
    for nv in G[v]:
        if not seen[nv]:
            dfs1(nv)
            c += childs[nv] + 1
    childs[v] = c
    return


dfs1(0)

numer = 0
seen = [False] * N

@lru_cache(maxsize=None)
def power(x, y, z):
    return pow(x, y, z)

def dfs2(v):
    global numer
    seen[v] = True
    nodes = []
    for nv in G[v]:
        if seen[nv]:
            nodes.append(N - childs[v] - 1)
        else:
            nodes.append(childs[nv] + 1)
    if len(nodes) > 1:
        this_numer = power(2, N - 1, MOD) - (sum(power(2, n, MOD) - 1 for n in nodes) + 1)
        numer = (numer + this_numer) % MOD
    for nv in G[v]:
        if not seen[nv]:
            dfs2(nv)
    return


dfs2(0)
denom = power(2, N, MOD)
ans = numer * pow(denom, MOD - 2, MOD) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit
from functools import lru_cache

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


MOD = 1000000007

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)

childs = [0] * N
seen = [False] * N


def dfs1(v):
    seen[v] = True
    c = 0
    for nv in G[v]:
        if not seen[nv]:
            dfs1(nv)
            c += childs[nv] + 1
    childs[v] = c
    return


dfs1(0)

numer = 0
seen = [False] * N

pow2 = pow(2, N - 1, MOD)

@lru_cache(maxsize=None)
def power(x, y, z):
    return pow(x, y, z)

def dfs2(v):
    global numer
    seen[v] = True
    nodes = []
    for nv in G[v]:
        if seen[nv]:
            nodes.append(N - childs[v] - 1)
        else:
            nodes.append(childs[nv] + 1)
    if len(nodes) > 1:
        this_numer = power(2, N - 1, MOD) - (sum(power(2, n, MOD) - 1 for n in nodes) + 1)
        numer = (numer + this_numer) % MOD
    for nv in G[v]:
        if not seen[nv]:
            dfs2(nv)
    return


dfs2(0)
denom = power(2, N, MOD)
ans = numer * pow(denom, MOD - 2, MOD) % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin, setrecursionlimit

setrecursionlimit(10 ** 9)
INF = 1 << 60


def input():
    return stdin.readline().strip()


MOD = 1000000007

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)

childs = [0] * N
seen = [False] * N
prev = [-1] * N


def dfs1(v):
    seen[v] = True
    c = 0
    for nv in G[v]:
        if not seen[nv]:
            prev[nv] = v
            dfs1(nv)
            c += childs[nv] + 1
    childs[v] = c
    return


dfs1(0)

numer = 0
seen = [False] * N

pow2 = pow(2, N - 1, MOD)


def dfs2(v):
    global numer
    seen[v] = True
    nodes = []
    if prev[v] != -1:
        nodes.append(N - childs[v] - 1)
    for nv in G[v]:
        if not seen[nv]:
            nodes.append(childs[nv] + 1)
    if len(nodes) > 1:
        this_numer = pow2 - (sum(pow(2, n, MOD) - 1 for n in nodes) + 1)
        numer = (numer + this_numer) % MOD
    for nv in G[v]:
        if not seen[nv]:
            dfs2(nv)
    return


dfs2(0)
denom = pow(2, N, MOD)
ans = numer * pow(denom, MOD - 2, MOD) % MOD
print(ans)

Submission status: Time Limit Exceeded

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

N = int(input())
edge = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    x, y = map(int, input().split())
    edge[x].append(y)
    edge[y].append(x)

# 頂点iから伸びてる枝それぞれのサイズ
ans = 0


def dfs(s, p=-1):
    global ans
    res = 1
    tmp = pow(2, N - 1, mod) - 1
    for t in edge[s]:
        if t == p:
            continue
        size = dfs(t, s)
        res += size
        tmp = (tmp - pow(2, size, mod) + 1 + mod) % mod
    if N != res:
        tmp = (tmp - pow(2, N - res, mod) + 1 + mod) % mod
    ans = (ans + tmp) % mod
    return res


dfs(1)
div = pow(2, N, mod)
ans = ans * pow(div, mod - 2, mod) % mod
print(ans)

Submission status: Time Limit Exceeded

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

N = int(input())
edge = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    x, y = map(int, input().split())
    edge[x].append(y)
    edge[y].append(x)

# 頂点iから伸びてる枝それぞれのサイズ
memo = [[] for _ in range(N + 1)]


def dfs(s, p=-1):
    res = 1
    for t in edge[s]:
        if t == p:
            continue
        size = dfs(t, s)
        memo[s].append(size)
        res += size
    if N != res:
        memo[s].append(N - res)
    return res


dfs(1)


cnt = 0
for lis in memo[1:]:
    if len(lis) == 1:
        continue
    # 頂点iが穴あきとならない->頂点から伸びてるやつ1つだけ黒の場合がダメ
    tmp = pow(2, N - 1, mod) - 1  # ぜんぶ白の場合を引いとく
    for x in lis:
        black = pow(2, x, mod) - 1
        tmp = (tmp - black + mod) % mod
    cnt = (cnt + tmp) % mod

div = pow(2, N, mod)
ans = cnt * pow(div, mod - 2, mod) % mod
print(ans)

Submission status: Time Limit Exceeded

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

N = int(input())
edge = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    x, y = map(int, input().split())
    edge[x].append(y)
    edge[y].append(x)

# 頂点iから伸びてる枝それぞれのサイズ
memo = [[] for _ in range(N + 1)]


def dfs(s, p=-1):
    sub_tree = []
    res = 1
    for t in edge[s]:
        if t == p:
            continue
        size = dfs(t, s)
        sub_tree.append(size)
        res += size
    if N != res:
        sub_tree.append(N - res)
    memo[s].extend(sub_tree)
    return res


dfs(1)


cnt = 0
for lis in memo[1:]:
    if len(lis) == 1:
        continue
    # 頂点iが穴あきとならない->頂点から伸びてるやつ1つだけ黒の場合がダメ
    tmp = pow(2, N - 1, mod) - 1  # ぜんぶ白の場合を引いとく
    for x in lis:
        black = pow(2, x, mod) - 1
        tmp = (tmp - black + mod) % mod
    cnt = (cnt + tmp) % mod

div = pow(2, N, mod)
ans = cnt * pow(div, mod - 2, mod) % mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from functools import lru_cache
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
mod = 10 ** 9 + 7

N = int(input())
edge = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    x, y = map(int, input().split())
    edge[x].append(y)
    edge[y].append(x)

# 頂点iから伸びてる枝それぞれのサイズ
memo = [[] for _ in range(N + 1)]


@lru_cache(maxsize=10**6)
def dfs(s, p=-1):
    sub_tree = []
    res = 1
    for t in edge[s]:
        if t == p:
            continue
        size = dfs(t, s)
        sub_tree.append(size)
        res += size
    if N != res:
        sub_tree.append(N - res)
    memo[s].extend(sub_tree)
    return res


dfs(1)


cnt = 0
for lis in memo[1:]:
    if len(lis) == 1:
        continue
    # 頂点iが穴あきとならない->頂点から伸びてるやつ1つだけ黒の場合がダメ
    tmp = pow(2, N - 1, mod) - 1  # ぜんぶ白の場合を引いとく
    for x in lis:
        black = pow(2, x, mod) - 1
        tmp = (tmp - black + mod) % mod
    cnt = (cnt + tmp) % mod

div = pow(2, N, mod)
ans = cnt * pow(div, mod - 2, mod) % mod
print(ans)

Submission status: Time Limit Exceeded

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

N = int(input())
edge = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    x, y = map(int, input().split())
    edge[x].append(y)
    edge[y].append(x)

# 頂点iから伸びてる枝それぞれのサイズ
memo = [[] for _ in range(N + 1)]


def dfs(s, p=-1):
    sub_tree = []
    for t in edge[s]:
        if t == p:
            continue
        sub_tree.append(dfs(t, s))
    memo[s].extend(sub_tree)
    return sum(sub_tree) + 1


dfs(1)
for i in range(2, N + 1):
    x = sum(memo[i])
    rest = N - x - 1
    memo[i].append(rest)


cnt = 0
for lis in memo[1:]:
    if len(lis) == 1:
        continue
    # 頂点iが穴あきとならない->頂点から伸びてるやつ1つだけ黒の場合がダメ
    tmp = pow(2, N - 1, mod) - 1  # ぜんぶ白の場合を引いとく
    for x in lis:
        black = pow(2, x, mod) - 1
        tmp = (tmp - black + mod) % mod
    cnt = (cnt + tmp) % mod

div = pow(2, N, mod)
ans = cnt * pow(div, mod - 2, mod) % mod
print(ans)

Submission status: Time Limit Exceeded

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


sys.setrecursionlimit(10**9)
from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')

#

def main():
	mod=10**9+7
	n=II()
	G=[[] for _ in range(n+1)]
	p=[0]*(n+1)
	v=[0]*(n+1)


	for _ in range(n-1):
		a,b=MI()
		G[a].append(b)
		G[b].append(a)

	inv2=[1]*(n+1)
	t=pow(pow(2,n,mod),mod-2,mod)
	for i in range(n,-1,-1):
		inv2[i]=t
		t*=2
		t%=mod
	#print(inv2)
	
	@lru_cache(maxsize=None)
	def dfs(a):
		cnt=1
		for i in G[a]:
			if p[a]==i:
				continue
			else:
				p[i]=a
				cnt+=dfs(i)
		v[a]=cnt
		return cnt
	dfs(1)
	#print(v)

	def f(a):
		return (1-inv2[a])*(1-inv2[n-a])%mod

	ans=1-inv2[n]-n*inv2[1]
	for i in range(1,n+1):
		ans+=f(v[i])%mod
	print(ans%mod)




if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

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


sys.setrecursionlimit(10**9)
from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')

#

def main():
	mod=10**9+7
	n=II()
	G=[[] for _ in range(n+1)]
	p=[0]*(n+1)
	v=[0]*(n+1)


	for _ in range(n-1):
		a,b=MI()
		G[a].append(b)
		G[b].append(a)

	inv2=[1]*(n+1)
	t=pow(pow(2,n,mod),mod-2,mod)
	for i in range(n,-1,-1):
		inv2[i]=t
		t*=2
		t%=mod
	#print(inv2)

	def dfs(a):
		cnt=1
		for i in G[a]:
			if p[a]==i:
				continue
			else:
				p[i]=a
				cnt+=dfs(i)
		v[a]=cnt
		return cnt
	dfs(1)
	#print(v)

	def f(a):
		return (1-inv2[a])*(1-inv2[n-a])%mod

	ans=1-inv2[n]-n*inv2[1]
	for i in range(1,n+1):
		ans+=f(v[i])%mod
	print(ans%mod)


if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

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


sys.setrecursionlimit(10**9)
from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')

#

def main():
	mod=10**9+7
	n=II()
	G=[[] for _ in range(n+1)]
	p=[0]*(n+1)
	v=[0]*(n+1)


	for _ in range(n-1):
		a,b=MI()
		G[a].append(b)
		G[b].append(a)

	inv2=[1]*(n+1)
	t=pow(pow(2,n,mod),mod-2,mod)
	for i in range(n,-1,-1):
		inv2[i]=t
		t*=2
		t%=mod
	#print(inv2)

	@lru_cache(maxsize=None)
	def dfs(a):
		cnt=1
		for i in G[a]:
			if p[a]==i:
				continue
			else:
				p[i]=a
				cnt+=dfs(i)
		v[a]=cnt
		return cnt
	dfs(1)
	#print(v)

	def f(a):
		return (1-inv2[a])*(1-inv2[n-a])%mod

	ans=1-inv2[n]-n*inv2[1]
	for i in range(1,n+1):
		ans+=f(v[i])%mod
	print(ans%mod)



















if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    input = stdin.readline
    mod = 10**9+7
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    pow2 = [1]
    for i in range(200000):
        pow2.append(pow2[-1]*2 % mod)

    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]
    root = 0
    d = [-1]*n
    d[root] = 0
    q = [root]
    cnt = 0
    while q:
        cnt += 1
        qq = []
        while q:
            i = q.pop()
            for j in g[i]:
                if d[j] == -1:
                    d[j] = cnt
                    qq.append(j)
        q = qq

    for i in range(n):
        di = d[i]
        g[i] = [j for j in g[i] if di <= d[j]]

    d = [j for i, j in sorted([(j, i) for i, j in enumerate(d)])]
    dp = [(0, 0, 1) for _ in [0]*n]

    for i in d[::-1]:
        if g:
            n = sum([dp[j][2] for j in g[i]])+1
            x, y = pow(2, n-1, mod)-1, 0
            for j in g[i]:
                xj, yj, nj = dp[j]
                p1, p2 = pow2[n-nj], pow2[nj]
                x += xj*p1+yj*(p1-1)-p2+1
                y += yj+p2-1
            dp[i] = (x % mod, y % mod, n)

    x = dp[0][0]
    y = pow(2, dp[0][2], mod)
    print(x*pow(y, mod-2, mod) % mod)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    input = stdin.readline
    mod = 10**9+7
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    pow2 = [1]
    for i in range(200000):
        pow2.append(pow2[-1]*2 % mod)

    g = [set() for _ in [0]*n]
    [g[a-1].add(b-1) for a, b in ab]
    [g[b-1].add(a-1) for a, b in ab]
    root = 0
    d = [-1]*n
    d[root] = 0
    q = [root]
    cnt = 0
    while q:
        cnt += 1
        qq = []
        while q:
            i = q.pop()
            for j in g[i]:
                if d[j] == -1:
                    d[j] = cnt
                    qq.append(j)
        q = qq

    for i in range(n):
        di = d[i]
        remove_list = set()
        for j in g[i]:
            if di > d[j]:
                remove_list.add(j)
        g[i] -= remove_list
    dd = [j for i, j in sorted([(j, i) for i, j in enumerate(d)])[::-1]]

    dp = [(0, 0, 1) for _ in [0]*n]
    for i in dd:
        if g:
            n = 1
            for j in g[i]:
                if j != i:
                    n += dp[j][2]
            x, y = pow(2, n-1, mod)-1, 0
            for j in g[i]:
                if j != i:
                    xj, yj, nj = dp[j]
                    p1, p2 = pow2[n-nj], pow2[nj]
                    x += xj*p1+yj*(p1-1)-p2+1
                    y += yj+p2-1
            dp[i] = (x % mod, y % mod, n)

    x = dp[0][0]
    y = pow(2, dp[0][2], mod)
    print(x*pow(y, mod-2, mod) % mod)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    input = stdin.readline
    mod = 10**9+7
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    pow2 = [1]
    for i in range(200000):
        pow2.append(pow2[-1]*2 % mod)

    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]
    root = 0
    d = [-1]*n
    d[root] = 0
    q = [root]
    cnt = 0
    while q:
        cnt += 1
        qq = []
        while q:
            i = q.pop()
            for j in g[i]:
                if d[j] == -1:
                    d[j] = cnt
                    qq.append(j)
        q = qq
    g2 = g
    g = [[] for _ in [0]*n]
    for i in range(n):
        di = d[i]
        g[i] = [j for j in g2[i] if di <= d[j]]

    dd = sorted([(j, i) for i, j in enumerate(d)])[::-1]
    dd = [j for i, j in dd]

    dp = [(0, 0, 1) for _ in [0]*n]
    for i in dd:
        if g:
            n = 1
            for j in g[i]:
                if j != i:
                    n += dp[j][2]
            x, y = pow(2, n-1, mod)-1, 0
            for j in g[i]:
                if j != i:
                    xj, yj, nj = dp[j]
                    p1, p2 = pow2[n-nj], pow2[nj]
                    x += xj*p1+yj*(p1-1)-p2+1
                    y += yj+p2-1
            dp[i] = (x % mod, y % mod, n)

    x = dp[0][0]
    y = pow(2, dp[0][2], mod)
    print(x*pow(y, mod-2, mod) % mod)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    input = stdin.readline
    mod = 10**9+7
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    pow2 = [1]
    for i in range(200000):
        pow2.append(pow2[-1]*2 % mod)

    g = [set() for _ in [0]*n]
    [g[a-1].add(b-1) for a, b in ab]
    [g[b-1].add(a-1) for a, b in ab]
    root = 0
    d = [-1]*n
    d[root] = 0
    q = [root]
    cnt = 0
    while q:
        cnt += 1
        qq = []
        while q:
            i = q.pop()
            for j in g[i]:
                if d[j] == -1:
                    d[j] = cnt
                    qq.append(j)
        q = qq

    for i in range(n):
        di = d[i]
        remove_list = []
        for j in g[i]:
            if di > d[j]:
                remove_list.append(j)
        for j in remove_list:
            g[i].remove(j)
    dd = sorted([(j, i) for i, j in enumerate(d)])[::-1]
    dd = [j for i, j in dd]

    dp = [(0, 0, 1) for _ in [0]*n]
    for i in dd:
        if g:
            n = 1
            for j in g[i]:
                if j != i:
                    n += dp[j][2]
            x, y = pow(2, n-1, mod)-1, 0
            for j in g[i]:
                if j != i:
                    xj, yj, nj = dp[j]
                    p1, p2 = pow2[n-nj], pow2[nj]
                    x += xj*p1+yj*(p1-1)-p2+1
                    y += yj+p2-1
            dp[i] = (x % mod, y % mod, n)

    x = dp[0][0]
    y = pow(2, dp[0][2], mod)
    print(x*pow(y, mod-2, mod) % mod)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    mod = 10**9+7
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    pow2 = [1]
    for i in range(200000):
        pow2.append(pow2[-1]*2 % mod)

    g = [set() for _ in [0]*n]
    [g[a-1].add(b-1) for a, b in ab]
    [g[b-1].add(a-1) for a, b in ab]
    root = 0
    d = [-1]*n
    d[root] = 0
    q = [root]
    cnt = 0
    while q:
        cnt += 1
        qq = []
        while q:
            i = q.pop()
            for j in g[i]:
                if d[j] == -1:
                    d[j] = cnt
                    qq.append(j)
        q = qq

    for i in range(n):
        di = d[i]
        remove_list = []
        for j in g[i]:
            if di > d[j]:
                remove_list.append(j)
        for j in remove_list:
            g[i].remove(j)
    dd = sorted([(j, i) for i, j in enumerate(d)])[::-1]
    dd = [j for i, j in dd]

    dp = [(0, 0, 1) for _ in [0]*n]
    for i in dd:
        if g:
            n = 1
            for j in g[i]:
                n += dp[j][2]
            x, y = pow(2, n-1, mod)-1, 0
            for j in g[i]:
                xj, yj, nj = dp[j]
                x += xj*pow2[n-nj]+yj * \
                    (pow2[n-nj]-1)-pow2[nj]+1
                y += yj+pow2[nj]-1
            dp[i] = (x % mod, y % mod, n)

    x = dp[0][0]
    y = pow(2, dp[0][2], mod)
    print(x*pow(y, mod-2, mod) % mod)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    mod = 10**9+7
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]

    g = [set() for _ in [0]*n]
    [g[a-1].add(b-1) for a, b in ab]
    [g[b-1].add(a-1) for a, b in ab]
    root = 0  # 根
    d = [-1]*n  # 根からの距離
    d[root] = 0
    q = [root]
    cnt = 0
    while q:  # BFS
        cnt += 1
        qq = []
        while q:
            i = q.pop()
            for j in g[i]:
                if d[j] == -1:
                    d[j] = cnt
                    qq.append(j)
        q = qq

    for i in range(n):
        di = d[i]
        remove_list = []
        for j in g[i]:
            if di > d[j]:
                remove_list.append(j)
        for j in remove_list:
            g[i].remove(j)
    dd = sorted([(j, i) for i, j in enumerate(d)])[::-1]
    dd = [j for i, j in dd]

    dp = [[0, 0, 1] for _ in [0]*n]
    for i in dd:
        if g:
            n = 1
            for j in g[i]:
                n += dp[j][2]
            x, y = pow(2, n-1, mod)-1, 0
            for j in g[i]:
                xj, yj, nj = dp[j]
                x += xj*pow(2, n-nj, mod)+yj * \
                    (pow(2, n-nj, mod)-1)-pow(2, nj, mod)+1
                y += yj+pow(2, nj, mod)-1
            dp[i] = [x % mod, y % mod, n]

    x = dp[0][0]
    y = pow(2, dp[0][2], mod)
    print(x*pow(y, mod-2, mod) % mod)


main()

Submission status: Time Limit Exceeded

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

class Segtree:
    def __init__(self, A, intv, initialize = True, segf = max):
        self.N = len(A)
        self.N0 = 2**(self.N-1).bit_length()
        self.intv = intv
        self.segf = segf
        if initialize:
            self.data = [intv]*self.N0 + A + [intv]*(self.N0 - self.N)
            for i in range(self.N0-1, 0, -1):
                self.data[i] = self.segf(self.data[2*i], self.data[2*i+1]) 
        else:
            self.data = [intv]*(2*self.N0)
        
    def update(self, k, x):
        k += self.N0
        self.data[k] = x
        while k > 0 :
            k = k >> 1
            self.data[k] = self.segf(self.data[2*k], self.data[2*k+1])
    
    def query(self, l, r):
        L, R = l+self.N0, r+self.N0
        s = self.intv
        while L < R:
            if R & 1:
                R -= 1
                s = self.segf(s, self.data[R])
            if L & 1:
                s = self.segf(s, self.data[L])
                L += 1
            L >>= 1
            R >>= 1
        return s
    
    def binsearch(self, l, r, check, reverse = False):
        L, R = l+self.N0, r+self.N0
        SL, SR = [], []
        while L < R:
            if R & 1:
                R -= 1
                SR.append(R)
            if L & 1:
                SL.append(L)
                L += 1
            L >>= 1
            R >>= 1
        
        if reverse:
            for idx in (SR + SL[::-1]):
                if check(self.data[idx]):
                    break
            else:
                return -1
            while idx < self.N0:
                if check(self.data[2*idx+1]):
                    idx = 2*idx + 1
                else:
                    idx = 2*idx
            return idx - self.N0
        else:
            for idx in (SL + SR[::-1]):
                if check(self.data[idx]):
                    break
            else:
                return -1
            while idx < self.N0:
                if check(self.data[2*idx]):
                    idx = 2*idx
                else:
                    idx = 2*idx + 1
            return idx - self.N0

def parorder(Edge, p):
    N = len(Edge)
    par = [0]*N
    par[p] = -1
    stack = [p]
    order = []
    visited = set([p])
    ast = stack.append
    apo = order.append
    while stack:
        vn = stack.pop()
        apo(vn)
        for vf in Edge[vn]:
            if vf in visited:
                continue
            visited.add(vf)
            par[vf] = vn
            ast(vf)
    return par, order

def getcld(p):
    res = [[] for _ in range(len(p))]
    for i, v in enumerate(p[1:], 1):
        res[v].append(i)
    return res


N = int(readline())
MOD = 10**9+7
Edge = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    Edge[a].append(b)
    Edge[b].append(a)


pow2 = [1]*(N+3)
for i in range(1, len(pow2)):
    pow2[i] = (2*pow2[i-1])%MOD
P, L = parorder(Edge, 0)
C = getcld(P)

dp1 = [0]*N
dp2 = [0]*N
size = [1]*N

for p in L[::-1]:
    sr = 1
    for c in C[p]:
        sr += size[c]
    size[p] = sr
    res1 = pow2[size[p]-1]-1
    res2 = pow2[size[p]-1]-1
    for c in C[p]:
        k = pow2[size[p]-1-size[c]]
        res1 = (res1 - (pow2[size[c]]-1) + dp1[c] + dp2[c]*(2*k-1))%MOD
        res2 = (res2 + 2*k*dp2[c])
    dp1[p] = res1
    dp2[p] = res2
print(dp1[0]*pow(pow(2, N, MOD), MOD-2, MOD)%MOD)

Submission status: Time Limit Exceeded

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

N = int(input())
MOD = 10**9 + 7
tree = [[] for i in range(N+1)]
for i in range(N-1):
  a, b = map(int, input().split())
  tree[a].append(b)
  tree[b].append(a)

# 頂点1をルートにして各頂点より下にある部分木の頂点数を求めていく
root, par = 1, 0
sizes = [0] * (N+1)
order = [[root, par]]
def calc_nums(node, par):
  global sizes
  global order
  if sizes[node] > 0:
    return sizes[node]
  children = tree[node]
  res = 1
  for child in children:
    if child == par:
      continue
    order.append([child, node])
    res += calc_nums(child, node)
  sizes[node] = res
  return res

_ = calc_nums(root, par)


# 各頂点について、その頂点が穴あき度としてカウントされる状況を独立に計算する
demo = 0 # 分子
div = pow(2, N, MOD) # 分母
base = pow(2, N-1, MOD) - 1
for node, par in order:
  children = tree[node]
  num = base
  num_par = N - 1
  for child in children:
    if child == par:
      continue
    s = sizes[child]
    num_par -= s
    num -= pow(2, s, MOD) - 1
  num -= pow(2, num_par, MOD) - 1
  demo += num
    
ans = demo * pow(div, MOD-2, MOD) % MOD
print(ans)