Problem:


Score : 600 points

Problem Statement

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

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

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

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

Notes

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

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

Constraints

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

1 \leq A_i,B_i \leq N

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

3
1 2
2 3

Sample Output 1

125000001

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

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

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

Sample Input 2

4
1 2
2 3
3 4

Sample Output 2

375000003

The expected holeyness is 3/8.

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

Sample Input 3

4
1 2
1 3
1 4

Sample Output 3

250000002

The expected holeyness is 1/4.

Sample Input 4

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

Sample Output 4

570312505



Sample input:
3
1 2
2 3


Sample output:
125000001

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(5+10**5)
mod=10**9+7
N=int(input())
G=[[] for i in range(N)]
for i in range(N-1):
    A,B=map(int,input().split())
    G[A-1].append(B-1)
    G[B-1].append(A-1)
Child=[[] for i in range(N)]

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

Submission status: Time Limit Exceeded

Solution code:
import os
import sys
from collections import defaultdict

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353

def div_mod(a, b, mod):
    return a * pow(b, mod - 2, mod) % mod


N = int(sys.stdin.buffer.readline())
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]

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

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

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


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


root = 0
dfs(root)

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(2*10**5)
mod=10**9+7
N=int(input())
G=[[] for i in range(N)]
for i in range(N-1):
    A,B=map(int,input().split())
    G[A-1].append(B-1)
    G[B-1].append(A-1)
Child=[[] for i in range(N)]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))

import sys
input = sys.stdin.readline


N = int(input())

d2 = [1]
for _ in range(N):
    d2.append(2*d2[-1]%mod)

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

v2i = [0 for _ in range(N+1)]
def itt(v, p):
    cn = 0
    ms = []
    for u in G[v]:
        if u == p:
            continue
        un = itt(u, v)
        ms.append(un)
        cn += un
    if p != None:
        ms.append(N-1-cn)
    v2i[v] = ms
    return cn+1
itt(1, None)
r = 0
for v in range(1, N+1):
    ff = v2i[v]
    for f in ff:
        r += d2[f] - 1 % mod
xx = d2[N]
print((div(N, 2) - div(N+r, xx))%mod)

Submission status: Time Limit Exceeded

Solution code:
import os
import sys
from collections import defaultdict

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353

def div_mod(a, b, mod):
    return a * pow(b, mod - 2, mod) % mod


N = int(sys.stdin.buffer.readline())
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]

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

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

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


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


root = 0
dfs(root)

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

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

Submission status: Time Limit Exceeded

Solution code:
import os
import sys
from collections import defaultdict

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353

def div_mod(a, b, mod):
    return a * pow(b, mod - 2, mod) % mod


N = int(sys.stdin.buffer.readline())
AB = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N - 1)]

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

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

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


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


root = 0
dfs(root)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))

import sys
from collections import defaultdict
input = sys.stdin.readline


N = int(input())

d2 = [1]
for _ in range(N):
    d2.append(2*d2[-1]%mod)

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

v2i = [0 for _ in range(N+1)]
def itt(v, p):
    cn = 0
    ms = []
    for u in G[v]:
        if u == p:
            continue
        un = itt(u, v)
        ms.append(un)
        cn += un
    if p != None:
        ms.append(N-1-cn)
    v2i[v] = ms
    return cn+1
itt(1, None)
r = 0
for v in range(1, N+1):
    ff = v2i[v]
    for f in ff:
        r += d2[f] - 1 % mod
xx = d2[N]
print((div(N, 2) - div(N+r, xx))%mod)

Submission status: Time Limit Exceeded

Solution code:
import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))

NNN = (10**5)
inverse = [0, 1]

for i in range( 2, NNN + 1 ):
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )


import sys
from collections import defaultdict
input = sys.stdin.readline

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

v2i = [0 for _ in range(N+1)]
def itt(v, p):
    cn = 0
    ms = []
    for u in G[v]:
        if u == p:
            continue
        un = itt(u, v)
        ms.append(un)
        cn += un
    if p != None:
        ms.append(N-1-cn)
    v2i[v] = ms
    return cn+1
itt(1, None)
r = 0
for v in range(1, N+1):
    ff = v2i[v]
    for f in ff:
        r += power(2, f) - 1 % mod
xx = power(2,N)
print((div(N, 2) - div(N+r, xx))%mod)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def MF(n,d): return ModFraction(n,d)

class ModFraction():
    def __init__(self, n, d):
        self.n = n
        self.d = d

    def __add__(self, x):
        xf = ModFraction.xf(x)
        a = self.n * xf.d % mod
        b = xf.n * self.d % mod
        c = self.d * xf.d % mod
        return ModFraction((a+b) % mod, c)

    def __sub__(self, x):
        xf = ModFraction.xf(x)
        a = self.n * xf.d % mod
        b = -xf.n * self.d % mod
        c = self.d * xf.d % mod
        return ModFraction((a+b) % mod, c)

    def __mul__(self, x):
        xf = ModFraction.xf(x)
        a = self.n * xf.n % mod
        b = self.d * xf.d % mod
        return ModFraction(a, b)

    def __truediv__(self, x):
        xf = ModFraction.xf(x)
        a = self.n * xf.d % mod
        b = self.d * xf.n % mod
        return ModFraction(a, b)

    @classmethod
    def xf(cls, x):
        if isinstance(x, int):
            return ModFraction(x, 1)
        return x

    @classmethod
    def inv(cls, x):
        return pow(x, mod - 2, mod)

    def int(self):
        return self.n * ModFraction.inv(self.d) % mod

    def __str__(self):
        return "{} / {}".format(self.n, self.d)


def main():
    n = I()
    e = collections.defaultdict(list)
    for _ in range(n-1):
        a,b = LI_()
        e[a].append(b)
        e[b].append(a)

    m = {}
    def f(i,p):
        k = i*n+p
        if k in m:
            return m[k]
        r = 1
        for c in e[i]:
            if c == p:
                continue
            r += f(c,i)
        m[k] = r
        m[p*n+i] = n - r
        return r

    pw = [1]
    for i in range(n):
        pw.append(pw[-1]*2%mod)

    r = 0
    for i in range(n):
        cs = []
        for c in e[i]:
            cs.append(f(c,i))
        t = sum(cs)
        for i in range(len(cs)-1):
            t -= cs[i]
            k = pw[cs[i]] - 1
            l = pw[t] - 1
            r += k * l % mod
            r %= mod

    rf = MF(r, pw[n])

    return rf.int()


print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def MF(n,d): return ModFraction(n,d)

class ModFraction():
    def __init__(self, n, d):
        self.n = n
        self.d = d

    def __add__(self, x):
        xf = ModFraction.xf(x)
        a = self.n * xf.d % mod
        b = xf.n * self.d % mod
        c = self.d * xf.d % mod
        return ModFraction((a+b) % mod, c)

    def __sub__(self, x):
        xf = ModFraction.xf(x)
        a = self.n * xf.d % mod
        b = -xf.n * self.d % mod
        c = self.d * xf.d % mod
        return ModFraction((a+b) % mod, c)

    def __mul__(self, x):
        xf = ModFraction.xf(x)
        a = self.n * xf.n % mod
        b = self.d * xf.d % mod
        return ModFraction(a, b)

    def __truediv__(self, x):
        xf = ModFraction.xf(x)
        a = self.n * xf.d % mod
        b = self.d * xf.n % mod
        return ModFraction(a, b)

    @classmethod
    def xf(cls, x):
        if isinstance(x, int):
            return ModFraction(x, 1)
        return x

    @classmethod
    def inv(cls, x):
        return pow(x, mod - 2, mod)

    def int(self):
        return self.n * ModFraction.inv(self.d) % mod

    def __str__(self):
        return "{} / {}".format(self.n, self.d)


def main():
    n = I()
    ab = [LI_() for _ in range(n-1)]
    e = collections.defaultdict(list)
    for a,b in ab:
        e[a].append(b)
        e[b].append(a)

    m = {}
    def f(i,p):
        k = i*n+p
        if k in m:
            return m[k]
        r = 1
        for c in e[i]:
            if c == p:
                continue
            r += f(c,i)
        m[k] = r
        m[p*n+i] = n - r
        return r

    pw = [1]
    for i in range(n):
        pw.append(pw[-1]*2%mod)

    r = 0
    for i in range(n):
        cs = []
        for c in e[i]:
            cs.append(f(c,i))
        t = sum(cs)
        for i in range(len(cs)-1):
            t -= cs[i]
            k = pw[cs[i]] - 1
            l = pw[t] - 1
            r += k * l % mod
            r %= mod

    rf = MF(r, pw[n])

    return rf.int()


print(main())

Submission status: Time Limit Exceeded

Solution code:
import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

import sys
from collections import defaultdict
input = sys.stdin.readline

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

v2i = [0 for _ in range(N+1)]
def itt(v, p):
    cn = 0
    ms = []
    for u in G[v]:
        if u == p:
            continue
        un = itt(u, v)
        ms.append(un)
        cn += un
    if p != None:
        ms.append(N-1-cn)
    v2i[v] = ms
    return cn+1
itt(1, None)
r = 0
for v in range(1, N+1):
    ff = v2i[v]
    for f in ff:
        r += power(2, f) - 1
xx = power(2,N-1)
print((div(N*xx-N-r, xx*2%mod))%mod)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def MF(n,d): return ModFraction(n,d)

class ModFraction():
    def __init__(self, n, d):
        self.n = n
        self.d = d

    def __add__(self, x):
        xf = ModFraction.xf(x)
        a = self.n * xf.d % mod
        b = xf.n * self.d % mod
        c = self.d * xf.d % mod
        return ModFraction((a+b) % mod, c)

    def __sub__(self, x):
        xf = ModFraction.xf(x)
        a = self.n * xf.d % mod
        b = -xf.n * self.d % mod
        c = self.d * xf.d % mod
        return ModFraction((a+b) % mod, c)

    def __mul__(self, x):
        xf = ModFraction.xf(x)
        a = self.n * xf.n % mod
        b = self.d * xf.d % mod
        return ModFraction(a, b)

    def __truediv__(self, x):
        xf = ModFraction.xf(x)
        a = self.n * xf.d % mod
        b = self.d * xf.n % mod
        return ModFraction(a, b)

    @classmethod
    def xf(cls, x):
        if isinstance(x, int):
            return ModFraction(x, 1)
        return x

    @classmethod
    def inv(cls, x):
        return pow(x, mod - 2, mod)

    def int(self):
        return self.n * ModFraction.inv(self.d) % mod

    def __str__(self):
        return "{} / {}".format(self.n, self.d)


def main():
    n = I()
    ab = [LI_() for _ in range(n-1)]
    e = collections.defaultdict(list)
    for a,b in ab:
        e[a].append(b)
        e[b].append(a)

    m = {}
    def f(i,p):
        k = (i,p)
        if k in m:
            return m[k]
        r = 1
        for c in e[i]:
            if c == p:
                continue
            r += f(c,i)
        m[k] = r
        m[(p,i)] = n - r
        return r

    pw = [1]
    for i in range(n):
        pw.append(pw[-1]*2%mod)

    r = 0
    for i in range(n):
        cs = []
        for c in e[i]:
            cs.append(f(c,i))
        t = sum(cs)
        for i in range(len(cs)-1):
            t -= cs[i]
            k = pw[cs[i]] - 1
            l = pw[t] - 1
            r += k * l % mod
            r %= mod

    rf = MF(r, pw[n])

    return rf.int()


print(main())

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools
import time,random

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


def MF(n,d): return ModFraction(n,d)

class ModFraction():
    def __init__(self, n, d):
        self.n = n
        self.d = d

    def __add__(self, x):
        xf = ModFraction.xf(x)
        a = self.n * xf.d % mod
        b = xf.n * self.d % mod
        c = self.d * xf.d % mod
        return ModFraction((a+b) % mod, c)

    def __sub__(self, x):
        xf = ModFraction.xf(x)
        a = self.n * xf.d % mod
        b = -xf.n * self.d % mod
        c = self.d * xf.d % mod
        return ModFraction((a+b) % mod, c)

    def __mul__(self, x):
        xf = ModFraction.xf(x)
        a = self.n * xf.n % mod
        b = self.d * xf.d % mod
        return ModFraction(a, b)

    def __truediv__(self, x):
        xf = ModFraction.xf(x)
        a = self.n * xf.d % mod
        b = self.d * xf.n % mod
        return ModFraction(a, b)

    @classmethod
    def xf(cls, x):
        if isinstance(x, int):
            return ModFraction(x, 1)
        return x

    @classmethod
    def inv(cls, x):
        return pow(x, mod - 2, mod)

    def int(self):
        return self.n * ModFraction.inv(self.d) % mod

    def __str__(self):
        return "{} / {}".format(self.n, self.d)


def main():
    n = I()
    ab = [LI_() for _ in range(n-1)]
    e = collections.defaultdict(list)
    for a,b in ab:
        e[a].append(b)
        e[b].append(a)

    m = {}
    def f(i,p):
        k = (i,p)
        if k in m:
            return m[k]
        kk = (p,i)
        if kk in m:
            m[k] = n - m[kk]
            return m[k]
        r = 1
        for c in e[i]:
            if c == p:
                continue
            r += f(c,i)
        m[k] = r
        return r

    pw = [1]
    for i in range(n):
        pw.append(pw[-1]*2%mod)

    r = 0
    for i in range(n):
        cs = []
        for c in e[i]:
            cs.append(f(c,i))
        t = sum(cs)
        for i in range(len(cs)-1):
            t -= cs[i]
            k = pw[cs[i]] - 1
            l = pw[t] - 1
            r += k * l % mod
            r %= mod

    rf = MF(r, pw[n])

    return rf.int()


print(main())

Submission status: Time Limit Exceeded

Solution code:
from collections import deque

LARGE = 10 ** 9 + 7


def solve(n, a_list, b_list):
    # root at 0
    g = [[] for _ in range(n)]
    for i in range(n - 1):
        a = a_list[i] - 1
        b = b_list[i] - 1
        g[a].append(b)
        g[b].append(a)

    parent = [-1] * n
    children = [[] for _ in range(n)]
    depth = [0] * n

    # find parent
    queue = deque([0])
    while len(queue) > 0:
        p = queue.popleft()
        for q in g[p]:
            if q == parent[p]:
                continue
            parent[q] = p
            children[p].append(q)
            depth[q] = depth[p] + 1
            queue.append(q)

    # weight
    weight = [1] * n
    deeper = list(sorted([[i, depth[i]] for i in range(n)], key=lambda x: x[1], reverse=True))
    for i, _ in deeper:
        for j in children[i]:
            weight[i] += weight[j]

    # calc
    res_array = [0] * n
    # P(i is not hole | i is white) = (other than one child( + parent) are all white)
    for i in range(1, n):
        for j in children[i]:
            res_array[n - 1 - weight[j]] += 1
        res_array[weight[i] - 1] += 1
        res_array[n - 1] -= len(children[i])
    for j in children[0]:
        res_array[n - 1 - weight[j]] += 1
    res_array[n - 1] -= len(children[0]) - 1
    # print(res_array)

    res_a = pow(2, n - 1, LARGE) * n
    res_a %= LARGE
    # print(res_a)
    for i in range(n):
        res_a -= pow(2, n - i - 1, LARGE) * res_array[i]
        res_a %= LARGE
        # print(res_a)
    res_b = pow(2, n, LARGE)

    res = res_a * pow(res_b, LARGE - 2, LARGE) % LARGE
    # print(res_a, res_b)
    return res


def main():
    n = int(input())
    a_list = [0] * (n - 1)
    b_list = [0] * (n - 1)
    for i in range(n - 1):
        a, b = map(int, input().split())
        a_list[i] = a
        b_list[i] = b
    res = solve(n, a_list, b_list)
    print(res)


def test():
    assert solve(3, [1, 2], [2, 3]) == 125000001
    assert solve(4, [1, 2, 3], [2, 3, 4]) == 375000003
    assert solve(4, [1, 1, 1], [2, 3, 4]) == 250000002


if __name__ == "__main__":
    test()
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0     : return 1
    elif y == 1     : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else            : return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

NNN = (10**5)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

import sys
from collections import defaultdict
input = sys.stdin.readline

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

v2i = [0 for _ in range(N+1)]
def itt(v, p):
    cn = 0
    ms = []
    for u in G[v]:
        if u == p:
            continue
        un = itt(u, v)
        ms.append(un)
        cn += un
    if p != None:
        ms.append(N-1-cn)
    v2i[v] = ms
    return cn+1
itt(1, None)
r = 0
for v in range(1, N+1):
    ff = v2i[v]
    for f in ff:
        r += power(2, f) - 1
print((div(N*power(2,N-1)-N-r, power(2, N)))%mod)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(2*10**5)
mod=10**9+7
N=int(input())
G=[[] for i in range(N)]
for i in range(N-1):
    A,B=map(int,input().split())
    G[A-1].append(B-1)
    G[B-1].append(A-1)
Child=[[] for i in range(N)]
reached=[0 for i in range(N)]
q=deque([])
q.append(0)
while(len(q)>0):
    r=q.popleft()
    reached[r]=1
    for p in G[r]:
        if reached[p]==1:
            continue
        Child[r].append(p)
        q.append(p)
#print(Child)
#print(Parents)
Childnum=[-1 for i in range(N)]
def dp(i):
    if Childnum[i]!=-1:
        return Childnum[i]
    if len(Child[i])==0:
        Childnum[i]=0
        return 0
    res=0
    for j in Child[i]:
        res+=dp(j)+1
    Childnum[i]=res
    return res
dp(0)
#print(Childnum)
def inv(x):
    return pow(x,mod-2,mod)
inv2=[inv(pow(2,i,mod)) for i in range(N+1)]
ans=(N*(1-inv(pow(2,N-1,mod))))%mod
for r in range(N):
    tmp=0
    for p in Child[r]:
        ai=Childnum[p]+1
        tmp+=ai
        k1=(1-inv2[ai])%mod
        k2=inv2[N-1-ai]
        #print(r,p,(k1*k2)%mod)
        ans-=(k1*k2)%mod
        ans%=mod
    ai=N-1-tmp
    k1=(1-inv2[ai])%mod
    k2=inv2[N-1-ai]
    ans-=(k1*k2)%mod
    #print(r,-1,(k1*k2)%mod)
    ans%=mod
print((ans*inv(2))%mod)

Submission status: Time Limit Exceeded

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, n):
    s = 0
    for nv in G[v]:
        if nv == p:
            continue
        res = dfs(v, nv, n+1)
        cnt[v].append(res)
        s+=res
    cnt[v].append(N-s-1)
    return s+1
dfs(-1, 0, 0) 
ans = 0
p = [1]*N
for i in range(1, N):
    p[i] = p[i-1]*2%mod
for v in range(N):
    if len(cnt[v])<=1:
        continue    
    res = p[N-1]-1
    for a in cnt[v]:
        res-=p[a]-1
    ans+=res
    ans%=mod
inv = pow(2, (mod-2)*N, mod)
print(ans*inv%mod)