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:
# rerootingは後で
from collections import deque
n=int(input())
e = [[] for _ in range(n)]

for i in range(n-1):
    ai,bi=map(int,input().split( ))
    ai-=1;bi-=1
    e[ai].append(bi)
    e[bi].append(ai)

deg = [len(e[i]) for i in range(n)]
dep0 = [-1]*n
dep0[0]=0

Q=deque();Q.append(0)

while Q:
    v=Q.popleft()
    for u in e[v]:
        if dep0[u]<0:
            dep0[u]=dep0[v]+1
            Q.append(u)
size = [1]*n
for i in range(n):
    flag=True
    for j in e[i]:
        if dep0[i]<dep0[j]:
            flag=False
            break
    if flag:
        Q.append(i)
while Q:
    v=Q.popleft()
    for u in e[v]:
        if dep0[u]<dep0[v]:
            size[u]+=size[v]
            deg[u]-=1
            if deg[u]==1 and u:
                Q.append(u)
ans=0
mod=10**9+7
x=pow(2,mod-2,mod)
#pw=[1]*(n+1)
pw_rev=[1]*(n+1)
for i in range(1,n+1):
    #pw[i] = pw[i-1] * 2 % mod
    pw_rev[i] = pw_rev[i-1] * x % mod
for u in range(n):
    for v in e[u]:
        if dep0[u]<dep0[v]:#dep
            ans += (1 - pw_rev[size[v]]) * (1 - pw_rev[n-size[v]])
    ans%=mod
## 空集合の場合
print((ans-n*x+1-pw_rev[n]) % mod)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7 # 998244353
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    n = int(input())
    E = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v = map(int,input().split())
        u -= 1; v -= 1;
        E[u].append(v)
        E[v].append(u)

    size = [1] * n
    stack = [(0, -1)]
    while stack:
        v, p = stack.pop()
        if v >= 0:
            for nv in E[v]:
                if nv == p:
                    continue
                stack.append((~nv, v))
                stack.append((nv, v))
        else:
            size[p] += size[~v]

    def rerooting(v, p):
        if p == -1:
            return
        size[p] -= size[v]
        size[v] += size[p]

    res = [None] * n
    stack = [(0, -1)]
    while stack:
        v, p = stack.pop()
        if v >= 0:
            rerooting(v, p)
            if res[v] is None:
                cnt = pow(2, n - 1, MOD)
                cnt -= 1
                for nv in E[v]:
                    cnt -= pow(2, size[nv], MOD) - 1
                res[v] = cnt % MOD
            for nv in E[v]:
                if nv == p:
                    continue
                stack.append((~nv, v))
                stack.append((nv, v))
        else:
            rerooting(p, ~v)

    print(sum(res) * pow(2, n * (MOD - 2) % (MOD - 1), MOD) % MOD)
resolve()

Submission status: Accepted

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

mod = 10**9+7

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

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

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


def func(x):
    return pow2[x]-1


class Tree:
    def __init__(self, crdinal, adjgrph, root, fnction=lambda x: 0):
        self.crdinal = crdinal
        self.adjgrph = adjgrph
        self.root = root
        self.fnction = fnction
        self.parent = [-1]*self.crdinal
        self.depth = [-1]*self.crdinal
        self.subsize = [1]*self.crdinal
        self.result = [0]*self.crdinal

        s = [root]
        while s:
            v = s.pop()
            if self.depth[v] == -1:
                if v == root:
                    self.depth[v] = 0
                else:
                    self.depth[v] = self.depth[self.parent[v]] + 1
                    s.append(v)
                for w in self.adjgrph[v]:
                    if self.depth[w] == -1:
                        self.parent[w] = v
                        s.append(w)
            else:
                self.subsize[self.parent[v]] += self.subsize[v]
                self.result[self.parent[v]] += self.fnction(self.subsize[v])

    def parent(self) -> list:
        return self.parent

    def depth(self) -> list:
        return self.depth

    def size(self) -> list:
        return self.subsize

    def result(self) -> list:
        return self.result


tr = Tree(n, g, 0, func)
sizesub = tr.subsize
black = tr.result


cnt = 0

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


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


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

Submission status: Accepted

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

mod = 10**9+7

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

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

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

par = [-1]*n
depth = [-1]*n
sizesub = [1 for _ in range(n)]
black = [0 for _ in range(n)]

root = 0
stack = [root]

while stack:
    v = stack.pop()
    if depth[v] == -1:
        if v == root:
            depth[v] = 0
        else:
            depth[v] = depth[par[v]] + 1
            stack.append(v)
        for w in g[v]:
            if depth[w] == -1:
                par[w] = v
                stack.append(w)
    else:
        sizesub[par[v]] += sizesub[v]
        black[par[v]] += pow2[sizesub[v]] - 1


cnt = 0

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


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


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

Submission status: Accepted

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

mod = 10**9+7

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

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

par = [-1]*n
depth = [-1]*n
sizesub = [1 for _ in range(n)]
black = [0 for _ in range(n)]

root = 0
stack = [root]

while stack:
    v = stack.pop()
    if depth[v] == -1:
        if v == root:
            depth[v] = 0
        else:
            depth[v] = depth[par[v]] + 1
            stack.append(v)
        for w in g[v]:
            if depth[w] == -1:
                par[w] = v
                stack.append(w)
    else:
        sizesub[par[v]] += sizesub[v]
        black[par[v]] += pow(2, sizesub[v], mod) - 1


cnt = 0

for i in range(n):
    tmp = pow(2, n-1, mod) - pow(2, n-sizesub[i], mod) - black[i]
    tmp %= mod
    cnt += tmp
    cnt %= mod


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


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

Submission status: Accepted

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)

dp1 = [0]*N
dp2 = [0]*N
size = [1]*N
for l in L[:0:-1]:
    p = P[l]
    size[p] += size[l]

for l in L[:0:-1]:
    p = P[l]
    dp1[l] = (dp1[l] + pow2[size[l]-1] - 1)%MOD
    dp2[l] = (dp2[l] + pow2[size[l]-1] - 1)%MOD
    k = pow2[size[p]-1-size[l]]
    dp1[p] = (dp1[p] - (pow2[size[l]]-1) + (2*k-1)*dp2[l] + dp1[l])%MOD
    dp2[p] = (dp2[p] + 2*dp2[l]*k)%MOD

dp1[0] = (dp1[0] + pow2[size[0]-1] - 1)%MOD
print(dp1[0]*pow(pow(2, N, MOD), MOD-2, MOD)%MOD)

Submission status: Accepted

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)

# 2の累乗を事前に計算しておく
prod2 = [1]
for i in range(N):
  prod2.append(prod2[-1] * 2 % MOD)

# 各頂点について、その頂点が穴あき度としてカウントされる状況を独立に計算する
demo = 0 # 分子
div = prod2[N] # 分母
base = prod2[N-1] - 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 -= prod2[s] - 1 
  num -= prod2[num_par] - 1
  demo += num
    
ans = demo * pow(div, MOD-2, MOD) % MOD
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
mod = 10**9 + 7

# 前準備
import sys
input = sys.stdin.readline
from collections import deque

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

ini = 0

# calcの定義 : 2辺を合わせる演算
def calc(a,b):
    return a+b

# dp1の更新
def calc1(c,p):
    p_num = ini
    for i in graph[c]:
        if i == p:
            continue
        p_num = calc(p_num, dp1[i])
    dp1[c] = (p_num+1) % mod

# dp2の更新　累積和チックにすることでうに対策。
def calc2(p):
    arr = [dp1[c] if c != parent[p] else dp2[p] for c in graph[p]]

    left = [ini]
    for i in arr[:-1]:
        left.append( calc(left[-1], i ) )
    right = [ini]
    for i in arr[:0:-1]:
        right.append( calc(right[-1], i) )
    right = right[::-1]

    prod = []
    for a,b in zip(left,right):
        prod.append( calc(a,b) )

    for c,x in zip(graph[p], prod):
        if(c != parent[p]):
            dp2[c] = (x + 1) % mod


# 根から探索して親と探索順を記録
root = 1
order = []
parent = [0] * (n+1)
stack = deque()
stack.append(root)
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        stack.append(y)
        parent[y] = x

# 親→子の値を算出
dp1 = [0] * (n+1)
for i in order[::-1]:
    calc1(i, parent[i])

# 子→親の値を算出
dp2 = [0] * (n+1)
for i in order:
    calc2(i)

ans = 0
for i in range(1,n+1):
    gr = graph[i]
    if(len(gr) == 1):
        continue
    tmp = pow(2,n-1,mod) - 1
    for v in gr:
        if(v == parent[i]):
            exp_num = dp2[i]
        else:
            exp_num = dp1[v]
        tmp = (tmp - (pow(2, exp_num, mod)-1)) % mod
    ans = (ans + tmp) % mod


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

Submission status: Accepted

Solution code:
import sys
import heapq as h

input=sys.stdin.readline

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

subtreesize=[1 for i in range(0,N)]
flag=[0 for i in range(0,N)]
q=[]
for i in range(1,N):
    if len(hen[i])==1:
        q.append(i)
        flag[i]=0

h.heapify(q)
sub=[]
h.heapify(sub)
while q!=[]:
    while q!=[]:
        x=h.heappop(q)
        for p in hen[x]:
            if p!=0:
                if flag[p]!=len(hen[p])-1:
                    subtreesize[p]+=subtreesize[x]
                    flag[p]+=1
                    if flag[p]==len(hen[p])-1:
                        h.heappush(sub,p)
            else:
                subtreesize[p]+=subtreesize[x]
        #何らかの操作
        #ここでsubキューに次に使うものを格納
        if q==[]:
            q=sub
            sub=[]
            h.heapify(sub)
            break

ans=[0 for i in range(0,N)]
flag=[0 for i in range(0,N)]
q=[]
for i in range(1,N):
    if len(hen[i])==1:
        q.append(i)
        flag[i]=0

h.heapify(q)
sub=[]
h.heapify(sub)
while q!=[]:
    while q!=[]:
        x=h.heappop(q)
        for p in hen[x]:
            if p!=0:
                if flag[p]!=len(hen[p])-1:
                    ans[p]=(ans[p]+ans[x]-pow(2,subtreesize[x],mod)+1)%mod
                    flag[p]+=1
                    if flag[p]==len(hen[p])-1:
                        ans[p]=(ans[p]+pow(2,N-1,mod)-pow(2,N-subtreesize[p],mod))%mod
                        h.heappush(sub,p)
            else:
                ans[p]=(ans[p]+ans[x]-pow(2,subtreesize[x],mod)+1)%mod
        #何らかの操作
        #ここでsubキューに次に使うものを格納
        if q==[]:
            q=sub
            sub=[]
            h.heapify(sub)
            break


ans[0]=(ans[0]+pow(2,N-1,mod)-1)%mod
print((ans[0]*pow(2,(N*(mod-2)),mod))%mod)

Submission status: Accepted

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]

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

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():
    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)
    d = [0]*n
    d[0] = 1
    q = deque([0])
    p = [None]*n
    while q:
        x = q.popleft()
        nd = d[x]+1
        for y in v[x]:
            if not d[y]:
                d[y] = nd
                p[y] = x
                q.append(y)
    V = list(range(n))
    V.sort(key = lambda x:-d[x])
    t = [1]*n
    for x in V[:-1]:
        t[p[x]] += t[x]
    ans = n
    for x in range(n):
        tx = t[x]
        for y in v[x]:
            ty = t[y]
            if tx < ty:
                ans += pow(2,t[0]-tx,mod)-1
            else:
                ans += pow(2,ty,mod)-1
        ans %= mod
    print((n*pow(2,mod-2,mod)-ans*pow(2,(mod-2)*n%(mod-1),mod))%mod)
    return

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

Submission status: Accepted

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():
    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)
    d = [0]*n
    d[0] = 1
    q = deque([0])
    p = [None]*n
    while q:
        x = q.popleft()
        nd = d[x]+1
        for y in v[x]:
            if not d[y]:
                d[y] = nd
                p[y] = x
                q.append(y)
    V = list(range(n))
    V.sort(key = lambda x:-d[x])
    t = [1]*n
    for x in V[:-1]:
        t[p[x]] += t[x]
    ans = n
    for x in range(n):
        tx = t[x]
        s = 0
        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((n*pow(2,mod-2,mod)-ans*pow(2,(mod-2)*n%(mod-1),mod))%mod)
    return

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

Submission status: Accepted

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():
    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)
    d = [0]*n
    d[0] = 1
    q = deque([0])
    p = [None]*n
    while q:
        x = q.popleft()
        nd = d[x]+1
        for y in v[x]:
            if not d[y]:
                d[y] = nd
                p[y] = x
                q.append(y)
    V = list(range(n))
    V.sort(key = lambda x:-d[x])
    t = [1]*n
    for x in V[:-1]:
        t[p[x]] += t[x]
    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-1),mod)%mod)
    return

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

Submission status: Accepted

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

mod = 10**9+7

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

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

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

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

depth[0] = 0
stack = [0]

while stack:
    v = stack.pop()
    if any(depth[w] == -1 for w in g[v]):
        stack.append(v)
    for w in g[v]:
        if depth[w] == -1:
            depth[w] = depth[v] + 1
            stack.append(w)
        elif depth[w] > depth[v]:
            ko_all[v] += ko_all[w] + 1
            ko_only[v] += pow2[ko_all[w]+1]-1


cnt = 0

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


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


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

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
mod=10**9+7
n=int(input())
edge=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)
inf=10**6
Par=[inf]*n
Par[0]=-1
Deg=[0]*n
Deg[0]=0
Chk=[0]
while Chk:
  c=Chk.pop()
  for next in edge[c]:
    if Par[next]==inf:
      Par[next]=c
      Deg[next]+=1
      Chk.append(next)

from collections import deque
TS=list(v for v in range(n) if Deg[v]==0)
D=deque(TS)
while D:
  v=D.popleft()
  for t in edge[v]:
    if t!=Par[v]:
      Deg[t]-=1
      if Deg[t]==0:
        D.append(t)
        TS.append(t)

Used=[False]*n
C=[0]*n
for i in reversed(range(n)):
  v=TS[i]
  Used[v]=True
  for g in edge[v]:
    if not Used[g]:
      C[g]+=C[v]+1

H=[0]*n
H[0]=1
H[1]=pow(2,mod-2,mod)
for i in range(2,n):
  H[i]=(H[i-1]*H[1])%mod

ans=0
for i in range(n):
  if len(edge[i])==1:
    continue
  else:
    A=[]
    for e in edge[i]:
      if e==Par[i]:
        A.append(n-1-C[i])
      else:
        A.append(C[e]+1)
    cur=1+(len(edge[i])-1)*H[-1]
    for a in A:
      cur-=H[n-1-a]
    ans+=cur
print((ans*H[1])%mod)

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
mod=10**9+7
n=int(input())
edge=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)
inf=10**6
Par=[inf]*n
Par[0]=-1
Deg=[0]*n
Deg[0]=0
Chk=[0]
while Chk:
  c=Chk.pop()
  for next in edge[c]:
    if Par[next]==inf:
      Par[next]=c
      Deg[next]+=1
      Chk.append(next)

from collections import deque
TS=list(v for v in range(n) if Deg[v]==0)
D=deque(TS)
while D:
  v=D.popleft()
  for t in edge[v]:
    if t!=Par[v]:
      Deg[t]-=1
      if Deg[t]==0:
        D.append(t)
        TS.append(t)

Used=[False]*n
C=[0]*n
for i in reversed(range(n)):
  v=TS[i]
  Used[v]=True
  for g in edge[v]:
    if not Used[g]:
      C[g]+=C[v]+1

H=[0]*n
H[0]=1
H[1]=pow(2,mod-2,mod)
for i in range(2,n):
  H[i]=(H[i-1]*H[1])%mod

ans=0
for i in range(n):
  if len(edge[i])==1:
    continue
  else:
    A=[]
    for e in edge[i]:
      if e==Par[i]:
        A.append(n-1-C[i])
      else:
        A.append(C[e]+1)
    cur=1+(len(edge[i])-1)*H[-1]
    for a in A:
      cur-=H[n-1-a]
    ans=(ans+cur)%mod
print((ans*H[1])%mod)

Submission status: Accepted

Solution code:
n = int(input())
G = [[] for _ in range(n)]
mod = 10**9 + 7

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

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

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

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

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

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

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


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

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
sys.setrecursionlimit(200000)
mod=10**9+7
n=int(input())
edge=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)
inf=10**6
Par=[inf]*n
Par[0]=-1
Chk=[0]
while Chk:
  c=Chk.pop()
  for next in edge[c]:
    if Par[next]==inf:
      Par[next]=c
      Chk.append(next)

C=[-1]*n
def ch(x):
  ret=0
  if x!=0 and len(edge[x])==1:
    C[x]=0
    return C[x]
  else:
    for e in edge[x]:
      if e==Par[x]:
        continue
      else:
        ret+=ch(e)+1
    C[x]=ret
    return C[x]
ch(0)

H=[0]*n
H[0]=1
H[1]=pow(2,mod-2,mod)
for i in range(2,n):
  H[i]=(H[i-1]*H[1])%mod

ans=0
for i in range(n):
  if len(edge[i])==1:
    continue
  else:
    A=[]
    for e in edge[i]:
      if e==Par[i]:
        A.append(n-1-C[i])
      else:
        A.append(C[e]+1)
    cur=1+(len(edge[i])-1)*H[-1]
    for a in A:
      cur-=H[n-1-a]
    ans=(ans+cur)%mod
print((ans*H[1])%mod)