Problem:


Score : 600 points

Problem Statement

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

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

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

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

Notes

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

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

Constraints

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

1 \leq A_i,B_i \leq N

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

3
1 2
2 3

Sample Output 1

125000001

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

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

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

Sample Input 2

4
1 2
2 3
3 4

Sample Output 2

375000003

The expected holeyness is 3/8.

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

Sample Input 3

4
1 2
1 3
1 4

Sample Output 3

250000002

The expected holeyness is 1/4.

Sample Input 4

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

Sample Output 4

570312505



Sample input:
3
1 2
2 3


Sample output:
125000001

Submission status: Accepted

Solution code:
def main():
    import sys
    input = lambda : sys.stdin.readline().rstrip()
    sys.setrecursionlimit(max(1000, 10**9))
    write = lambda x: sys.stdout.write(x+"\n")


    ### 木の読み込み tree

    # サイズが大きいとdefaultdictが早い(for文を書かなくて済む)
    from collections import defaultdict
    # import numpy as np
    # from numba import njit
    n = int(input())
    ns = defaultdict(set)
    for _ in range(n-1):
        u,v = map(int, input().split())
        u -= 1
        v -= 1
        ns[u].add(v)
        ns[v].add(u)


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

    bs[0,-1] = 0
    for u,_ in reversed(done):
        p = parent[u]
        for v in ns[u]:
            if v==p:
                continue
            bs[v,u] = bs[p,u] - bs[u,v] + bs[u,p]

    M = 10**9 + 7
    p1 = pow(2, n-1, M)
    p2 = pow(2, n, M)
    p3 = pow(p2, M-2, M)
    ans = 0
    for u in range(n):
        s = 0
        for v in ns[u]:
            s += pow(2, bs[u,v], M) - 1
            s %= M
        val = p1 - s - 1
        ans += val
        ans %= M
    ans *= p3
    ans %= M
    print(ans%M)
# from line_profiler import LineProfiler
# lp = LineProfiler()
# lp.add_function(main)
# lp.runcall(main)
# lp.print_stats()
main()

Submission status: Accepted

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

N = int(readline())
m = map(int,read().split())
AB = zip(m,m)

MOD = 10 ** 9 + 7

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

root = 1
parent = [0] * (N+1)
order = []
stack = [root]
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)

# (1/2)^n
x = (MOD + 1) // 2
power = [1] * (N+100)
power_inv = [1] * (N+100)
for i in range(1,N+100):
    power[i] = power[i-1] * 2 % MOD
    power_inv[i] = power_inv[i-1] * x % MOD

# 部分木の大きさ
answer = 0
size = [1] * (N+1)
for v in order[::-1]:
    p = parent[v]
    size[p] += size[v]
    A = [size[w] for w in graph[v] if w != p] # 部分木のサイズ集合
    if v != root:
        A.append(N - 1 - sum(A))
    if len(A) == 1:
        continue
    prod = 1
    coef = 1
    for x in A:
        prod *= power_inv[x]
        prod %= MOD
        coef += (power[x] - 1)
    E = 1 - prod * coef % MOD
    answer += E

answer *= power_inv[1]
answer %= MOD
print(answer)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
mod = 10 ** 9 + 7
e = [[] for _ in range(N + 1)]
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append(v)
  e[v].append(u)

s = [1]
order = []
parent = [0] * (N + 1)
size = [1] * (N + 1)
vis = [0] * (N + 1)
while len(s):
  x = s.pop()
  order.append(x)
  vis[x] = 1
  for y in e[x]:
    if vis[y]: continue
    s.append(y)
    vis[y] = 1
    parent[y] = x

order.reverse()
for y in order[: -1]: size[parent[y]] += size[y]
#print(size)

rev = lambda x: pow(x, mod - 2, mod)
res = rev(2) - rev(pow(2, N, mod))
res %= mod
for y in e[1]:
  res -= rev(pow(2, N - size[y], mod)) * (1 - rev(pow(2, size[y], mod)))
  res %= mod
#print(res)

order.reverse()
for y in order[1: ]:
  t = rev(2) - rev(pow(2, N, mod))
  x = parent[y]
  #print(t)
  for z in e[y]:
    if x == z: continue
    t -= rev(pow(2, N - size[z], mod)) * (1 - rev(pow(2, size[z], mod)))
    t %= mod
  #print(t)
  t -= rev(pow(2, size[y], mod)) * (1 - rev(pow(2, N - size[y], mod)))
  t %= mod
  res += t
  res %= mod
  #print(t)
print(res)

Submission status: Accepted

Solution code:
#解説方針#解法1
#https://qiita.com/ZhangChaoran/items/71fab0e4b8647a93d3a0
from collections import deque
from heapq import heappop, heappush
#標準入力
N = int(input())
MOD = 10 ** 9 + 7
L = [[] for i in range(N + 1)] #dfs用
for i in range(N - 1):
  a, b = map(int, input().split())
  L[a].append(b)
  L[b].append(a)

#木の探索
parent = [0] * (N + 1)
order = []
stack = [1]
while stack:
    x = stack.pop()
    order.append(x)  # 行きがけ順探索リスト
    for y in L[x]:
        if y == parent[x]:
            continue
        parent[y] = x  # 親ノードを記録
        stack.append(y)
#print(order, parent)

half = pow(2, MOD - 2, MOD)
power_inv = [1] * (N + 1)#2 ** N の逆元の集合
size = [1] * (N + 1)
for i, v in enumerate(order[::-1], 1):#iが1から
    p = parent[v]
    x = size[v]  # vの子孫ノード数（自分も含む）をとる
    size[p] += x  # 親にノード数を加算
    power_inv[i] = power_inv[i - 1] * half % MOD  # [1, 1/2, 1/4, ...]
#print(size)
# 辺iがSに含まれるための必要十分条件による辺の個数の期待値 
# (1 - (1/2) ** i)(1 - (1/2) ** (N - i))を展開して計算
# 根である1の頂点以外は、ある頂点とその親を結ぶ辺を考えた際
# i と N - i個の頂点に別れるので,size[2:]でOK
ans = sum((1 - power_inv[i] - power_inv[N - i] + power_inv[N]) %
          MOD for i in size[2:])  
#ans = sum((1 - (1/2) ** i- (1/2) ** (N - i) + (1/2) ** N) for i in size[2:])  
#print(ans)
ans += 1  # 木の頂点の個数は辺の個数+1
# -「すべての辺が含まれない、つまり空グラフの場合の誤加算」-N/2
ans -= power_inv[N] + N * power_inv[1]  
#ans -= N * power_inv[1]  
ans %= MOD

print(ans)

Submission status: Accepted

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

def solve():
    MOD = 10**9 + 7

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

    sizeSubtrees = [0] * N
    sizeAdjss = [[] for _ in range(N)]

    def dfs(vNow, vPar):
        sizeSubtrees[vNow] = 1
        for v2 in adjL[vNow]:
            if v2 == vPar: continue
            s = dfs(v2, vNow)
            sizeAdjss[vNow].append(s)
            sizeSubtrees[vNow] += s
        sizeAdjss[vNow].append(N-sizeSubtrees[vNow])
        return sizeSubtrees[vNow]

    dfs(0, -1)

    def getPows(base, n, MOD):
        pows = [1] * (n+1)
        for x in range(1, n+1):
            pows[x] = (pows[x-1] * base) % MOD
        return pows
    pow2s = getPows(2, N, MOD)

    nums = [0] * N
    for v in range(N):
        num = pow2s[N-1] - 1
        for sizeAdj in sizeAdjss[v]:
            num -= pow2s[sizeAdj] - 1
            num %= MOD
        nums[v] = num

    ans = sum(nums) % MOD * pow(pow2s[N], MOD-2, MOD) % MOD
    print(ans)


solve()

Submission status: Accepted

Solution code:
from collections import deque


def topological_sort_tree(tree: list, root) -> list:
    """根付き木をトポロジカルソートする"""
    n = len(tree)
    ans = [root]
    visited = [False] * n
    visited[root] = True
    q = deque([root])
    while q:
        par = q.popleft()
        for child in tree[par]:
            if visited[child]:
                continue
            visited[child] = True
            q.append(child)
            ans.append(child)
    return ans


n = int(input())
info = [list(map(int, input().split())) for i in range(n - 1)]
MOD = 10 ** 9 + 7


tree = [[] for i in range(n)]
for a, b in info:
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)


inv2 = pow(2, MOD - 2, MOD)
ans = 0
tp_sorted = topological_sort_tree(tree, 0)[::-1]
dp = [0] * n
for v in tp_sorted:
    sum_ = 0
    w_p = []
    for nxt_v in tree[v]:
        sum_ += dp[nxt_v]
        if dp[nxt_v] != 0:
            w_p.append(pow(inv2, dp[nxt_v], MOD))
    dp[v] = sum_ + 1

    if len(tree[v]) == 1:
        continue
    if n - dp[v] != 0:
        w_p.append(pow(inv2, n - dp[v], MOD))

    res = 1
    all_w = 1
    for val in w_p:
        all_w *= val
        all_w %= MOD
    res -= all_w
    res %= MOD

    for val in w_p:
        b = 1 - val
        res -= all_w * pow(val, MOD - 2, MOD) * b
        res %= MOD
    ans += res * inv2
    ans %= MOD

print(ans % MOD)

Submission status: Accepted

Solution code:
# ref https://qiita.com/ZhangChaoran/items/71fab0e4b8647a93d3a0
from collections import deque
import sys
input = sys.stdin.readline

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

mod = 10**9 + 7
par = [0] * (n + 1)
order = []
stk = deque()
stk.append(1)

while stk:
    v = stk.pop()
    order.append(v)
    for x in g[v]:
        if x == par[v]:
            continue
        par[x] = v
        stk.append(x)

rev = (mod + 1) // 2
po2_inv = [1] * (n + 1)
size = [1] * (n + 1)
for i, y in enumerate(order[::-1], 1):
    p = par[y]
    size[p] += size[y]
    po2_inv[i] = po2_inv[i - 1] * rev % mod

ans = 1
for i in size[2:]:
    ans += (1 - po2_inv[i] - po2_inv[n - i] + po2_inv[n]) % mod
ans -= po2_inv[n] + n * po2_inv[1]
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
# ref https://qiita.com/ZhangChaoran/items/71fab0e4b8647a93d3a0
from collections import deque
import sys
input = sys.stdin.readline

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

mod = 10**9 + 7
par = [0] * (n + 1)
order = []
stk = deque()
stk.append(1)

while stk:
    v = stk.pop()
    order.append(v)
    for x in g[v]:
        if x == par[v]:
            continue
        par[x] = v
        stk.append(x)

rev = pow(2, mod - 2, mod)
po2_inv = [1] * (n + 1)
size = [1] * (n + 1)
for i, y in enumerate(order[::-1], 1):
    p = par[y]
    size[p] += size[y]
    po2_inv[i] = po2_inv[i - 1] * rev % mod

ans = 1
for i in size[2:]:
    ans += (1 - po2_inv[i] - po2_inv[n - i] + po2_inv[n]) % mod
ans -= po2_inv[n] + n * po2_inv[1]
ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.buffer.read


def main():
    MOD = 1000000007
    N, *AB = map(int, read().split())
    G = [[] for _ in range(N)]
    for a, b in zip(AB[::2], AB[1::2]):
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)

    stack = deque([0])
    order = []
    prev = [0] * N
    prev[0] = -1
    while stack:
        v = stack.pop()
        order.append(v)
        for nv in G[v]:
            if nv != prev[v]:
                stack.append(nv)
                prev[nv] = v

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

    nodes = [1] * N
    numer = 0

    for v in reversed(order):
        if prev[v] != -1:
            nodes[prev[v]] += nodes[v]
        numer = (numer + pow2[N - 1] - pow2[N - nodes[v]]) % MOD
        for nv in G[v]:
            if nv != prev[v]:
                numer = (numer - pow2[nodes[nv]] + 1) % MOD

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.buffer.read


def main():
    MOD = 1000000007
    N, *AB = map(int, read().split())
    G = [[] for _ in range(N)]
    for a, b in zip(AB[::2], AB[1::2]):
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)

    stack = deque([0])
    order = []
    prev = [0] * N
    prev[0] = -1
    while stack:
        v = stack.pop()
        order.append(v)
        for nv in G[v]:
            if nv != prev[v]:
                stack.append(nv)
                prev[nv] = v

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

    nodes = [1] * N
    numer = 0

    for v in reversed(order):
        if prev[v] != -1:
            nodes[prev[v]] += nodes[v]
        numer = (numer + pow2[N - 1] - 1 - (pow2[N - nodes[v]] - 1)) % MOD
        for nv in G[v]:
            if nv != prev[v]:
                numer = (numer - (pow2[nodes[nv]] - 1)) % MOD

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    MOD = 1000000007
    N, *AB = map(int, read().split())
    G = [[] for _ in range(N)]
    for a, b in zip(AB[::2], AB[1::2]):
        G[a - 1].append(b - 1)
        G[b - 1].append(a - 1)

    stack = deque([0])
    order = []
    prev = [0] * N
    prev[0] = -1
    while stack:
        v = stack.pop()
        order.append(v)
        for nv in G[v]:
            if nv != prev[v]:
                stack.append(nv)
                prev[nv] = v

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

    nodes = [1] * N
    numer = 0

    for v in reversed(order):
        if prev[v] != -1:
            nodes[prev[v]] += nodes[v]
        numer = (numer + pow2[N - 1] - 1 - (pow2[N - nodes[v]] - 1)) % MOD
        for nv in G[v]:
            if nv != prev[v]:
                numer = (numer - (pow2[nodes[nv]] - 1)) % MOD

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

    cs = [1] * N
    def dfs(v,p=-1):
        ret = 1
        for to in es[v]:
            if to==p: continue
            ret += dfs(to,v)
        cs[v] = ret
        return ret
    dfs(0)

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

    ans = 0
    for i in range(N):
        if len(es[i]) == 1: continue
        ans += pow2[N-1] - 1
        c = 0
        for to in es[i]:
            if cs[to] > cs[i]: continue
            c += cs[to]
            ans -= pow2[cs[to]] - 1
        ans -= pow2[N-c-1] - 1

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

Submission status: Accepted

Solution code:
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
from collections import deque
con = 10 ** 9 + 7; INF = float("inf")

def getlist():
	return list(map(int, input().split()))

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

def DFS(G, W, Wlist, visit, node):
	for i in G.graph[node]:
		if visit[i] == 0:
			visit[i] = 1
			DFS(G, W, Wlist, visit, i)
			W[node] += W[i]
			Wlist.append(W[i])

class BFS(object):
	def __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = deque(); self.Q.append(s)
		self.dist = [INF] * N; self.dist[s] = 0
		self.prev = [None] * N; self.prev[s] = -1
		self.order = []
		while self.Q:
			v = self.Q.popleft()
			self.order.append(v)
			for i in self.g[v]:
				if self.dist[i] == INF:
					self.dist[i] = self.dist[v] + 1
					self.prev[i] = v
					self.Q.append(i)


#処理内容
def main():
	#入力
	N = int(input())
	G = Graph()
	Nedge = [0] * N
	for i in range(N - 1):
		a, b = getlist()
		a -= 1; b -= 1
		G.add_edge(a, b)
		G.add_edge(b, a)
		Nedge[a] += 1; Nedge[b] += 1

	W = [1] * N
	#葉の場合の処理
	# for i in range(N):
	# 	if Nedge[i] == 1:
	# 		W[i] = 1

	BF = BFS(G, 0, N)

	for i in range(N - 1, 0, -1):
		v = BF.order[i]
		W[BF.prev[v]] += W[v]

	Wlist = []
	for i in range(N):
		for j in G.graph[i]:
			if j != BF.prev[i]:
				Wlist.append(W[j])
	for i in range(N):
		Wlist.append(N - W[i])

	pow2 = pow(2, N - 1, con)
	ans_up = N * (pow2 - 1)
	for i in Wlist:
		ans_up -= pow(2, i, con) - 1
		ans_up %= con

	ans = ans_up * pow(pow2 * 2, con - 2, con)
	print(ans % con)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
deg = [0]*(n+1)
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
  deg[a] += 1
  deg[b] += 1
stack = []
root = -1
for i in range(1,n+1):
  if deg[i] == 1:
    stack.append(i)
  elif root == -1:
    root = i
deg[root] += 1
dp = [[] for i in range(n+1)]
num = [0]*(n+1)
while stack:
  x = stack.pop()
  if dp[x]:
    num[x] = sum(dp[x])+1
  else:
    num[x] = 1
  for y in graph[x]:
    if deg[y] > 1:
      dp[y].append(num[x])
      deg[y] -= 1
      if deg[y] == 1:
        stack.append(y)
for i in range(1,n+1):
  if num[i] != n:
    dp[i].append(n-num[i])
ans = 0
mod = 10**9+7
def inv(x):
  return pow(x,mod-2,mod)
inv2 = inv(2)
inv2n = inv(pow(2,n,mod))
for i in range(1,n+1):
  if len(dp[i]) > 1:
    ans += 1
    ans -= inv2
    ans += inv2n*(len(dp[i])-1)
    for val in dp[i]:
      ans -= pow(2,val,mod)*inv2n
      ans %= mod
print(ans)

Submission status: Accepted

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

readline = sys.stdin.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))


n = ni()
G = [list() for _ in range(n)]
for _ in range(n-1):
  a, b = nm()
  a -= 1; b -= 1
  G[a].append(b)
  G[b].append(a)
  
  
mod = 10**9 + 7
dub = [1]*(n+1)
for i in range(n):
  dub[i+1] = dub[i] * 2
  if dub[i+1] > mod:
    dub[i+1] -= mod
    
size = [1]*n
def dfs_depandsize(tree,v,p):
    for x in tree[v]:
        if x == p:
            continue
        size[v] += dfs_depandsize(tree,x,v)
    return size[v]
dfs_depandsize(G, 0, -1)
ans = 0
for v in range(n):
  c = 0
  res = 1
  for x in G[v]:
    if size[x] < size[v]:
      c += size[x]
      res += dub[size[x]] - 1
  res += dub[n-1-c] - 1
  res %= mod
  ans = (ans + dub[n-1] - res) % mod
print(ans * pow(dub[n], mod-2, mod) % mod)

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))


n = ni()
G = [list() for _ in range(n)]
for _ in range(n-1):
  a, b = nm()
  a -= 1; b -= 1
  G[a].append(b)
  G[b].append(a)
  
  
mod = 10**9 + 7
dub = [1]*(n+1)
for i in range(n):
  dub[i+1] = dub[i] * 2
  if dub[i+1] > mod:
    dub[i+1] -= mod
    
size = [-1]*n
q = [0]
while q:
  v = q[-1]
  if size[v] < 0:
    for x in G[v]:
      if size[x] < 0:
        q.append(x)
    size[v] = 0
  else:
    size[v] = 1
    for x in G[v]:
      size[v] += size[x]
    q.pop()

ans = 0
for v in range(n):
  c = 0
  res = 1
  for x in G[v]:
    if size[x] < size[v]:
      c += size[x]
      res += dub[size[x]] - 1
  res += dub[n-1-c] - 1
  res %= mod
  ans = (ans + dub[n-1] - res) % mod
print(ans * pow(dub[n], mod-2, mod) % mod)

Submission status: Accepted

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)

    pows = []
    for i in range(N + 1):
        pows.append(pow(2, i, MOD))

    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 = pows[N - 1]
        tmp -= 1 # all white
        for sub in subs:
            #tmp -= pow(2, sub, MOD) - 1
            tmp -= pows[sub] - 1
        num[0] += tmp
        return children + 1
    dfs(0)

    #deno = pow(2, N, MOD)
    deno = pows[N]
    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: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from collections import deque

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


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)

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

order = []
parent = [-1] * N

stack = deque([0])
while stack:
    v = stack.pop()
    order.append(v)
    for nv in G[v]:
        if parent[v] != nv:
            parent[nv] = v
            stack.append(nv)

numer = 0
nums = [0] * N

for v in reversed(order):
    tmp = 1
    for nv in G[v]:
        if parent[v] != nv:
            nums[v] += nums[nv] + 1
            tmp += pow2[nums[nv] + 1] - 1
    tmp += pow2[N - nums[v] - 1] - 1
    numer = (numer + pow2[N - 1] - tmp) % MOD

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

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from collections import deque

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


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


MOD = 1000000007
N = int(stdin.buffer.readline())
m = map(int, stdin.buffer.read().split())
AB = zip(m, m)
G = [[] for _ in range(N)]
for a, b in AB:
    G[a - 1].append(b - 1)
    G[b - 1].append(a - 1)

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

order = []
parent = [-1] * N

stack = deque([0])
while stack:
    v = stack.pop()
    order.append(v)
    for nv in G[v]:
        if parent[v] != nv:
            parent[nv] = v
            stack.append(nv)

numer = 0
nums = [0] * N

for v in reversed(order):
    tmp = 1
    for nv in G[v]:
        if parent[v] != nv:
            nums[v] += nums[nv] + 1
            tmp += pow2[nums[nv] + 1] - 1
    tmp += pow2[N - nums[v] - 1] - 1
    numer = (numer + pow2[N - 1] - tmp) % MOD

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

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from collections import deque

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)

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

order = []
parent = [-1] * N

stack = deque([0])
while stack:
    v = stack.pop()
    order.append(v)
    for nv in G[v]:
        if parent[v] != nv:
            parent[nv] = v
            stack.append(nv)

numer = 0
nums = [0] * N

for v in reversed(order):
    tmp = 1
    for nv in G[v]:
        if parent[v] != nv:
            nums[v] += nums[nv] + 1
            tmp += pow2[nums[nv] + 1] - 1
    tmp += pow2[N - nums[v] - 1] - 1
    numer = (numer + pow2[N - 1] - tmp) % MOD

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

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from collections import deque

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)

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

order = []
parent = [-1] * N

stack = deque([0])
while stack:
    v = stack.pop()
    order.append(v)
    for nv in G[v]:
        if parent[v] != nv:
            parent[nv] = v
            stack.append(nv)

numer = 0
nums = [0] * N

for v in reversed(order):
    tmp = 1
    for nv in G[v]:
        if parent[v] != nv:
            c = nums[nv] + 1
            nums[v] += c
            tmp += pow2[c] - 1
    tmp += pow2[N - nums[v] - 1] - 1
    numer = (numer + pow2[N - 1] - tmp) % MOD

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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


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


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

Submission status: Accepted

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

Solution code:
n=int(input())
mod=10**9+7
edge=[[] for i in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    edge[a].append(b)
    edge[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
    
import sys
sys.setrecursionlimit(10**6)
dep=[-1 for i in range(n+1)]
ans=[0]
def f(a):
    return inv2[n-a]*(1-inv2[a])%mod
def dfs(s,d):
    dep[s]=d
    tmp=inv2[1]-inv2[n]
    y=0
    for i in edge[s]:
        if dep[i]==-1:
            x=dfs(i,d+1)
            tmp-=f(x)
            y+=x
    if y==0:
        return 1
    tmp-=f(n-y-1)
    ans[0]+=tmp
    ans[0]%=mod
    return y+1
dfs(1,0)
print(ans[0])