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: Wrong Answer

Solution code:
# 75

import sys
from fractions import Fraction
sys.setrecursionlimit(10**8)

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


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


def modpow(a, n):
    # calc : (a**n)%MOD
    ret = 1
    while n > 0:
        if n & 1:
            ret = (ret * a) % MOD
        a = (a * a) % MOD
        n >>= 1
    return ret


def modinv(a):
    # calc : (a**(-1)) %MOD
    return modpow(a, MOD-2)


dfs(0)

ans = 0
for i in range(1, N):
    ans += (1 - (1/2)**num_l[i]) * (1 - (1/2)**(N-num_l[i]))
ans += 1 - (1/2)**N  # 辺の期待値→頂点の期待値に変換(空集合以外は+1される)
ans -= N/2  # 黒点の期待値を引く

tmp = Fraction(ans)
x = tmp.denominator
y = tmp.numerator

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

print(z)

Submission status: Wrong Answer

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

"""
ある頂点が白のとき，穴あき度の総和に与える影響を考える，
入力例2の1-2-3-4なら(0,3,3,0)この頂点2に注目，この3は，上下どちらもに黒があれば良い．上(2^1 - 1) * 下(2^2 - 1)=3．つまり全量 - all白

実際には子が多い．どこか2箇所の部分木に黒があれば良い=>余事象．
・全量：pow(2,N-1)，自分は白確定，墓はなんでも良い

・all白=1通り
・1個の部分木が黒*1通り（*1は残りall白の分）
「1この部分木が黒」はどう求める？　その部分木のサイズをnとして，2^n - 1．
その部分木のサイズはどう求める？　全方位木DPか=>端の頂点から詰めていけばいけそう

"""

def main():
    mod=10**9+7
    import queue
        
    N=I()
    adj=[[]for _ in range(N)]
    for i in range(N-1):
        x,y=MI()
        x-=1
        y-=1
        adj[x].append(y)
        adj[y].append(x)
        
    #2べきを持っておくか，
    POW=[1]
    for _ in range(N+5):
        temp=POW[-1]
        POW.append((temp*2)%mod)
    
    L=[[]for _ in range(N)]#　各頂点からみて，個を根とする部分木のサイズを配列として持っておく    
    
    looked=[0]*N#qに突っ込むか
    used=[0]*N#計算を終えたか
    q=queue.Queue()
    
    for v in range(N):
        if len(adj[v])==1:
            q.put(v)
            L[v].append(0)
            looked[v]=1
            
    ans=[0]*N
    while not q.empty():
        v=q.get()
        S=sum(L[v])
        rem=N-S-1#まだ見ていない方向の合計
        temp=POW[N-1]#全体
        temp-=1#all白
        
        for s in L[v]:#1つの部分木にだけ黒があるパターンを引く
            temp-=POW[s]-1
            temp%=mod
            
        if rem!=0:
            temp-=POW[rem]-1
            temp%=mod
            
        ans[v]=temp
        
        for nv in adj[v]:
            if looked[nv]==0:
                q.put(nv)
                looked[nv]=1
            if used[nv]==0:
                L[nv].append(S+1)
                
                
    # print(ans)
    y=sum(ans)
    x=POW[N]
    
    res=(y*pow(x,mod-2,mod))%mod
    print(res)
    
        
    
        
    
    

main()

Submission status: Wrong Answer

Solution code:
import os
import sys
import numpy as np

def solve(N, AB):
    mod = 10**9+7
    half = mod // 2 + 1
    G = [[0]*0 for _ in range(N+1)]
    for i in range(len(AB)):
        a, b = AB[i]
        G[a].append(b)
        G[b].append(a)
    P = [0] * (N+1)
    Size = [0] * (N+1)
    def dfs(v):
        # siz = 1
        # p = P[v]
        # for u in G[v]:
        #     if u != p:
        #         P[u] = v
        #         dfs(u)
        #         siz += Size[u]
        # Size[v] = siz
        st = [(v, 0)]
        while st:
            v, state = st.pop()
            p = P[v]
            if state == 0:
                st.append((v, 1))
                Size[v] = 1
                for u in G[v]:
                    if u != p:
                        P[u] = v
                        st.append((u, 0))
            else:
                Size[p] += Size[v]
    dfs(1)
    ans = 0
    Prob = [0]
    h = 1
    for i in range(202020):
        h = h * half % mod
        Prob.append(1-h)
    for v in range(1, len(G)):
        siz_v = Size[v]
        Gv = G[v]
        if v == 1:
            ps = [0]*0
        else:
            ps = [Prob[N-siz_v]]
        par = P[v]
        for u in Gv:
            if par != u:
                siz_u = Size[u]
                ps.append(Prob[siz_u])
        if len(ps)<=1:
            continue
        cumprod1_ps = [1, 1]
        cumprod2_ps = [1, 1]
        cp = 1
        for p in ps:
            cp = cp * (1-p) % mod
            cumprod1_ps.append(cp)
        cp = 1
        for p in ps[::-1]:
            cp = cp * (1-p) % mod
            cumprod2_ps.append(cp)
        cumprod2_ps.reverse()
        an = 1 - cumprod1_ps[-1]
        for j in range(1, len(cumprod1_ps)-1):
            cp1 = cumprod1_ps[j]
            cp2 = cumprod2_ps[j]
            p = ps[j-1]
            an -= cp1 * cp2 % mod * p
        ans += an
    ans = ans % mod * half % mod
    return ans


# >>> numba compile >>>
numba_config = [
    [solve, "i8(i8,i8[:,:])"],
]
if sys.argv[-1] == "ONLINE_JUDGE":
    from numba import njit
    from numba.pycc import CC
    cc = CC("my_module")
    for func, signature in numba_config:
        vars()[func.__name__] = njit(signature)(func)
        cc.export(func.__name__, signature)(func)
    cc.compile()
    exit()
elif os.name == "posix":
    exec(f"from my_module import {','.join(func.__name__ for func, _ in numba_config)}")
else:
    from numba import njit
    for func, signature in numba_config:
        vars()[func.__name__] = njit(signature, cache=True)(func)
    print("compiled!", file=sys.stderr)
# <<< numba compile <<<


def main():
    sys.setrecursionlimit(505050)
    input = sys.stdin.buffer.readline
    N = int(input())
    AB = np.array(sys.stdin.buffer.read().split(), dtype=np.int64).reshape(N - 1, 2)
    ans = solve(N, AB)
    print(ans)

main()

Submission status: Wrong Answer

Solution code:
#解説方針#解法1
from collections import deque
#標準入力
N = int(input())
mod = 10 ** 9 + 7
L = [[] for i in range(N + 1)] #dfs用
AB = [0] * (N - 1)
for i in range(N - 1):
  a, b = map(int, input().split())
  L[a].append(b)
  L[b].append(a)
  AB[i] = [a, b]
#print(L)
#逆元計算
#P = 10 ** 9 + 7
#N2 = 2 * 100000 + 1
#inv_t = [0]+[1]
#for i in range(2,N2):
#  inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

#各辺がSに含まれる確率を求める
def dfs(c, d):#辺をつなぐ2頂点を変数にとる
  q = deque([c])
  visited = [0] * (N + 1)
  visited[c] = 1
  visited[d] = 1
  ans = 1
  while q:
    e = q.pop()
    for i in L[e]:
      if visited[i] == 0:
        visited[i] = 1
        ans += 1
        q.append(i)
  #print(ans , N - ans)
  pro = (1-((1/2) ** ans)) * (1-((1/2) ** (N - ans)))
  return pro      

#頂点の個数の期待値にする。
#基本的に辺の数+1だが、黒の頂点が一つもない1パターン(確率 1 / 2**N)だけ別に考慮
x = 0
for i in range(N - 1):
  x += dfs(AB[i][0], AB[i][1])
x = x + 1 - (N / 2) - (1/2) ** N
print(x)#期待値があっていることを確認

Submission status: Wrong Answer

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())
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: Wrong Answer

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: Wrong Answer

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: Wrong Answer

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


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: Wrong Answer

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])
	print(ans)



















if __name__ == "__main__":
	main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9 +7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

N = inputI()
l = inputILL(N-1)

dic = dict([(i,[]) for i in range(1,N+1)])

for i in l:
  dic[i[0]].append(i[1])
  dic[i[1]].append(i[0])


d = [[INF,i] for i in range(N+1)]
d[1][0] = 0
q = deque([1])

while q:
  x = q.popleft()
  nd = d[x][0]+1
  for nx in dic[x]:
    if nd < d[nx][0]:
      d[nx][0] = nd
      q.append(nx)


d_ = sorted(d[1:],reverse=True)
n = [1 for _ in range(N+1)]

for item in d_:
  depth = item[0]
  i = item[1]
  for j in dic[i]:
    if d[j][0] == depth+1:
      n[i] += n[j]

print(n)
ans = (pow(2,N,MOD)-N*pow(2,N-1,MOD)-1)%MOD
for i in range(2,N+1):
  ans = (ans + (pow(2,n[i],MOD)-1) * (pow(2,N-n[i],MOD)-1)) % MOD

print((ans*inv(pow(2,N,MOD)))%MOD)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def dfs(x):
        res = 1
        for y in v[x]:
            if d[y]:
                d[y] = 0
                res += dfs(y)
        t[x] = res
        return res

    n = I()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    t = [0]*n
    d = [1]*n
    d[0] = 0
    dfs(0)
    ans = 0
    p = pow(2,n-1,mod)
    for x in range(n):
        tx = t[x]
        if len(v[x]) < 2:
            continue
        s = p-1
        for y in v[x]:
            ty = t[y]
            if tx < ty:
                s -= pow(2,t[0]-tx,mod)-1
            else:
                s -= pow(2,ty,mod)-1
            s %= mod
        ans += s
        ans %= mod
    print(ans*pow(2,(mod-2)*n%mod,mod)%mod)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

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

N = int(readline())
graph = [[] for _ in range(N + 1)]
for i in range(N - 1):
    a, b = map(int, readline().split())
    graph[a].append(b)
    graph[b].append(a)

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

MOD = 10**9 + 7
half = pow(2, MOD - 2, MOD)
power_inv = [1] * (N + 1)
size = [1] * (N + 1)
for i, v in enumerate(order[::-1], 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, ...]

ans = (1 - power_inv[N]) + sum((1 - power_inv[i] - power_inv[N - i] + power_inv[N]) % MOD for i in size[2:])  # 解法1の確率式(ノード1を除く)
ans += (1 - power_inv[N]) - N * power_inv[1]  # +  - N/2 
ans %= MOD

print(ans)

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    v = [[] for i in range(n)]
    f = [0]*n
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        f[a] += 1
        f[b] += 1
        v[a].append(b)
        v[b].append(a)
    q = deque([i for i in range(n) if f[i] == 1])
    size = [0]*n
    con = [0]*n
    for i in q:
        size[i] = 1
        con[i] = 1
    while q:
        x = q.popleft()
        con[x] = 1
        for y in v[x]:
            if size[y] == 0:
                size[y] = 1
                q.append(y)
            if not con[y]:
                size[y] += size[x]
    r = x
    inv = pow(2,mod-2,mod)
    ans = (1-pow(inv,n,mod)-n*inv)%mod
    p = [pow(inv,i,mod) for i in range(n)]
    for i in range(n):
        if i == r:
            continue
        a = size[i]
        b = n-a
        ans += (p[a]-1)*(p[b]-1)%mod
        ans %= mod
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    v = [[] for i in range(n)]
    f = [0]*n
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        f[a] += 1
        f[b] += 1
        v[a].append(b)
        v[b].append(a)
    q = deque([i for i in range(n) if f[i] == 1])
    size = [0]*n
    con = [0]*n
    r = q[0]
    for i in q:
        size[i] = 1
        con[i] = 1
    while q:
        x = q.popleft()
        con[x] = 1
        for y in v[x]:
            if size[y] == 0:
                q.append(y)
            if not con[y]:
                size[y] += size[x]
    inv = pow(2,mod-2,mod)
    ans = (1-pow(inv,n,mod)-n*inv)%mod
    p = [pow(inv,i,mod) for i in range(n)]
    for i in range(n):
        if i == r:
            continue
        a = size[i]
        b = n-a
        ans += (p[a]-1)*(p[b]-1)%mod
        ans %= mod
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n = I()
    v = [[] for i in range(n)]
    f = [0]*n
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        f[a] += 1
        f[b] += 1
        v[a].append(b)
        v[b].append(a)
    q = deque([i for i in range(n) if f[i] == 1])
    size = [0]*n
    con = [0]*n
    for i in q:
        size[i] = 1
        con[i] = 1
    while q:
        x = q.popleft()
        con[x] = 1
        for y in v[x]:
            if size[y] == 0:
                q.append(y)
            if not con[y]:
                size[y] += size[x]
    inv = pow(2,mod-2,mod)
    ans = (1-pow(inv,n,mod)-n*inv)%mod
    p = [pow(inv,i,mod) for i in range(n)]
    for i in range(1,n):
        a = size[i]
        b = n-a
        ans += (p[a]-1)*(p[b]-1)%mod
        ans %= mod
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def dfs(x,d):
        d[x] = 0
        for y in v[x]:
            if d[y]:
                size[x] += dfs(y,d)
        return size[x]

    n = I()
    v = [[] for i in range(n)]
    size = [1]*n
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    d = [1]*n
    dfs(0,d)
    inv = pow(2,mod-2,mod)
    ans = (1-pow(inv,n,mod)-n*inv)%mod
    p = [pow(inv,i,mod) for i in range(n)]
    for i in range(1,n):
        a = size[0]-size[i]
        b = n-a
        ans += (1-p[a])*(1-p[b])%mod
        if ans > mod:
            ans %= mod
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Wrong Answer

Solution code:
N = int(input())
C = [0] * N
mod = 10**9 + 7
x = 2**N % mod
y = (N*(1 + 2**(N-1)) - 2) % mod
for i in range(N-1):
	l, r = map(int, input().split())
	C[l-1] = C[l-1] + 1
	C[r-1] = C[r-1] + 1
C.remove(max(C))
for i in C:
	y = (y - (2**(i) % mod) - (2**(N-i) % mod)) % mod

t = 1
while True:
	if (y + mod * t) % x == 0:
		print(int((y + mod * t) / x))
		break
	else:
		t += 1

Submission status: Wrong Answer

Solution code:
N = int(input())
C = [[]] * N
S = [[]] * N
x = 2**N
y = N*(1 + 2**(N-1)) - 2
for i in range(N-1):
	l, r = map(int, input().split())
	if r not in C[l-1]:
		C[l-1] = C[l-1] + [r]
		S[l-1] = S[l-1] + [0]
	if l not in C[r-1]:
		C[r-1] = C[r-1] + [l]
		S[r-1] = S[r-1] + [0]

cnt = 0
sumn = 0
while cnt < 2*N -2:
	for i in range(N):
		if S[i].count(0) == 1:
			ind = S[i].index(0)
			ind2 = C[C[i][ind]-1].index(i+1)
			y -= 2**(sum(S[i])+1) + 2**(N-1-sum(S[i]))
			S[C[i][ind]-1] = S[C[i][ind]-1][:ind2] +[sum(S[i])+1] + S[C[i][ind]-1][ind2 + 1:]
			S[i] = S[i][:ind] +[N-1-sum(S[i])] + S[i][ind + 1:]
			cnt += 2

mod = 10**9 + 7
t = 1
while True:
	if (y + mod * t) % x == 0:
		print(int((y + mod * t) / x))
		break
	else:
		t += 1

Submission status: Wrong Answer

Solution code:
from numpy import *

N = int(input())
A = zeros((N-1,2), int)
for i in range(N-1):
	A[i][0], A[i][1] = map(int, input().split())
C = [[]] * N

for i in range(N):
	C[i] = list(A[where(A == (i+1))[0],abs(where(A == (i+1))[1]-1)])
hole = []


def sizeof(branch):
	size = 1
	for i in C[branch[1]-1]:
		if i != branch[0]:
			size += sizeof([branch[1], i])
	return size


def getexpt(nod, branches):
	if len(branches) == 1:
		return 0
	pos = 0
	for i in branches:
		pos += 2**sizeof([nod + 1, i])
	re = 2**(N-1) + len(branches) - 1 - pos
	return re


x = 2**N
y = 0
for i in range(N):
	y += getexpt(i, C[i])

mod = 10**9 + 7
t = 1
while True:
	if (y + mod * t) % x == 0:
		print(int((y + mod * t) / x))
		break
	else:
		t += 1

Submission status: Wrong Answer

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)

exit()
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: Wrong Answer

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

Submission status: Wrong Answer

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