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
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

MOD = 10 ** 9 + 7
def my_pow(base, n, mod):
    if n == 0:
        return 1
    x = base
    y = 1
    while n > 1:
        if n % 2 == 0:
            x *= x
            n //= 2
        else:
            y *= x
            n -= 1
        x %= mod
        y %= mod
    return x * y % mod

N = int(input())

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

ans = 0
def dfs(v, p):
    global ans
    subs = []
    res = 1
    for u in adj[v]:
        if u == p:
            continue
        val = dfs(u, v)
        res += val
        subs.append(val)
    # add sub-tree on the parent side
    if p != -1:
        subs.append(N - res)
    now = my_pow(2, N - 1, MOD) - 1 # N - 1 means that it chooses freelye other than v
    for sub in subs:
        now -= my_pow(2, sub, MOD) - 1
    ans += now
    ans %= MOD
    return res

dfs(0, -1)
print(ans * my_pow(2 ** N, MOD - 2, MOD) % MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

MOD = 10 ** 9 + 7
def my_pow(base, n, mod):
    if n == 0:
        return 1
    x = base
    y = 1
    while n > 1:
        if n % 2 == 0:
            x *= x
            n //= 2
        else:
            y *= x
            n -= 1
        x %= mod
        y %= mod
    return x * y % mod

N = int(input())

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

ans = 0
def dfs(v, p):
    global ans
    subs = []
    res = 1
    for u in adj[v]:
        if u == p:
            continue
        val = dfs(u, v)
        res += val
        subs.append(val)
    # add sub-tree on the parent side
    if p != -1:
        subs.append(N - res)
    now = (2 ** (N - 1)) - 1 # N - 1 means that it chooses freelye other than v
    now %= MOD
    for sub in subs:
        now -= ((2 ** sub) - 1)
        now %= MOD
    ans += now
    ans %= MOD
    return res

dfs(0, -1)
print(ans * my_pow(2 ** N, MOD - 2, MOD) % MOD)

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

MOD = 10 ** 9 + 7
def my_pow(base, n, mod):
    if n == 0:
        return 1
    x = base
    y = 1
    while n > 1:
        if n % 2 == 0:
            x *= x
            n //= 2
        else:
            y *= x
            n -= 1
        x %= mod
        y %= mod
    return x * y % mod

N = int(input())

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

ans = 0
def dfs(v, p):
    global ans
    subs = []
    res = 1
    for u in adj[v]:
        if u == p:
            continue
        val = dfs(u, v)
        res += val
        subs.append(val)
    # add sub-tree on the parent side
    if p != -1:
        subs.append(N - res)
    now = (2 ** (N - 1)) - 1 # N - 1 means that it chooses freelye other than v
    for sub in subs:
        now -= ((2 ** sub) - 1)
    ans += now
    ans %= MOD
    return res

dfs(0, -1)
print(ans * my_pow(2 ** N, MOD - 2, MOD) % MOD)

Submission status: Time Limit Exceeded

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


    ### 木の読み込み tree

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


    bs = {}    

    def sub(u, p):
        if (p,u) in bs:
            return bs[p,u]
        bs[p,u] = 1 + sum(sub(v,u) for v in ns[u] if v!=p)
        return bs[p,u]

    def sub2(u, p):
        for v in ns[u]:
            if v==p:
                continue
            bs[v,u] = bs[v,u] = bs[p,u] - bs[u,v] + bs[u,p]
            sub2(v,u)

    sub(0, -1)
    bs[0,-1] = 0
    sub2(0,-1)
    # ans[0] = bs[-1,0]
    bs[0,-1] = 0
    M = 10**9 + 7
    p1 = pow(2, n-1, M)
    p2 = pow(2, n, M)
    p3 = pow(p2, M-2, M)
    ans = 0
    for u in range(n):
        s = 0
        for v in ns[u]:
            s += pow(2, bs[u,v], M) - 1
            s %= M
        val = p1 - s - 1
        ans += val
        ans %= M
    ans *= p3
    ans %= M
    print(ans%M)
main()

Submission status: Time Limit Exceeded

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


    ### 木の読み込み tree

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


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

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

    M = 10**9 + 7
    p1 = pow(2, n-1, M)
    p2 = pow(2, n, M)
    p3 = pow(p2, M-2, M)
    ans = 0
    for u in range(n):
        s = 0
        for v in ns[u]:
            s += pow(2, bs[u,v], M) - 1
            s %= M
        val = p1 - s - 1
        ans += val
        ans %= M
    ans *= p3
    ans %= M
    print(ans%M)
main()

Submission status: Time Limit Exceeded

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


### 木の読み込み tree

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


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

M = 10**9 + 7
p1 = pow(2, n-1, M)
p2 = pow(2, n, M)
p3 = pow(p2, M-2, M)
ans = 0
for u in range(n):
    s = 0
    for v in ns[u]:
        s += pow(2, bs[u,v], M) - 1
        s %= M
    val = p1 - s - 1
    ans += val
    ans %= M
ans *= p3
ans %= M
print(ans%M)

Submission status: Time Limit Exceeded

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


### 木の読み込み tree

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

bs = {}
def sub(u, p):
    if (p,u) in bs:
        return bs[p,u]
    b = 1
    ps = []
    for v in ns[u]:
        if v==p:
            continue
        bb = sub(v, u)
        b += bb
    bs[p,u] = b
    return b

def sub2(u, p):
    for v in ns[u]:
        if v==p:
            continue
        b1 = bs[p,u]
        b2 = bs[u,v]
        b3 = bs[u,p]
        # 逆向き枝の計算
        bb = b1 - b2 + b3
        bs[v,u] = bb
        sub2(v,u)
        
sub(0, -1)
bs[0,-1] = 0
sub2(0,-1)
# ans[0] = bs[-1,0]
M = 10**9 + 7
p1 = pow(2, n-1, M)
p2 = pow(2, n, M)
p3 = pow(p2, M-2, M)
ans = 0
for u in range(n):
    s = 0
    for v in ns[u]:
        s += pow(2, bs[u,v], M) - 1
    val = p1 - s - 1
    ans += val
#     print(val)
    ans %= M
ans *= p3
ans %= M
print(ans%M)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import deque

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


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

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

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

    nodes = [1] * N
    numer = 0

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

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import heapq
import copy
  
N = int(input())
ab = [[] * (N + 1) for i in range(N + 1)]
E = [0] * (N - 1)
for i in range(N - 1):
  a, b = map(int, input().split())
  ab[a].append(b)
  ab[b].append(a)
  E[i] = [a, b]
#print(ab)

#xとyを根とする部分木の頂点の数を求める
#辺xy を切り離して考える
def dfs(x, y):
  q = copy.deepcopy(ab[x])
  count = 1
  visited = [0] * (N + 1)
  visited[x] = 1
  #print(q, visited)
  while q:
    now = heapq.heappop(q)
    visited[now] = 1
    if now != y:
      count += 1
      for i in ab[now]:
        if visited[i] == 0:
          heapq.heappush(q, i)
  return count

#print(dfs(2, 3))
#(1 - (1/ 2) ** c) * (1 - (1/ 2) ** (N - c)) + 1
#上式を辺ごとに全て足し合わせたものがSの頂点の個数の期待値
#そこからN / 2を引けば求める期待値
#逆元を考える必要があるため、分母と分子に分けて考える

t = 2 ** N#分母
s = 0#分子
for i in range(N - 1):
  c = dfs(E[i][0], E[i][1])
  #print(c)
  s += (2 ** N + 1 - 2 ** (N - c) - 2 ** c) 
  
#辺の個数を数えたので、それに2 ** Nを足して、頂点の個数にする
#-1は空グラフをケア
s += 2 ** N - 1  
s -= N * 2 ** (N - 1)

#逆元計算
p = 10 ** 9 + 7
t_inv = pow(t, p-2, p)
ans = t_inv * s % p
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
import copy
  
N = int(input())
ab = [[] * (N + 1) for i in range(N + 1)]
E = [0] * (N - 1)
for i in range(N - 1):
  a, b = map(int, input().split())
  ab[a].append(b)
  ab[b].append(a)
  E[i] = [a, b]
#print(ab)

#xとyを根とする部分木の頂点の数を求める
#辺xy を切り離して考える
def dfs(x, y):
  q = copy.deepcopy(ab[x])
  count = 1
  visited = [0] * (N + 1)
  visited[x] = 1
  #print(q, visited)
  while q:
    now = heapq.heappop(q)
    visited[now] = 1
    #if x == 3:
    #  print(q, now, visited)
    #  print(ab)
    if now != y:
      count += 1
      for i in range(len(ab[now])):
        if visited[ab[now][i]] == 0:
          heapq.heappush(q, ab[now][i])
  return count

#print(dfs(2, 3))
#(1 - (1/ 2) ** c) * (1 - (1/ 2) ** (N - c)) + 1
#上式を辺ごとに全て足し合わせたものがSの頂点の個数の期待値
#そこからN / 2を引けば求める期待値
#逆元を考える必要があるため、分母と分子に分けて考える

t = 2 ** N#分母
s = 0#分子
for i in range(N - 1):
  c = dfs(E[i][0], E[i][1])
  #print(c)
  s += (2 ** N + 1 - 2 ** (N - c) - 2 ** c) 
  
#辺の個数を数えたので、それに2 ** Nを足して、頂点の個数にする
#-1は空グラフをケア
s += 2 ** N - 1  
s -= N * 2 ** (N - 1)

#逆元計算
p = 10 ** 9 + 7
t_inv = pow(t, p-2, p)
ans = t_inv * s % p
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
AB = []
query = [[] for _ in range(N)]
mod = 10**9+7
import sys
sys.setrecursionlimit(10**6)
for _ in range(N-1):
    a, b = map(int, input().split())
    query[a-1].append(b-1)
    query[b-1].append(a-1)
    AB.append((a-1, b-1))

edges = [0]*N
def dfs(b, v):
    lis = []
    cum = 0
    lis = query[v]
    for i in lis:
        if i==b:
            continue
        cum += dfs(v, i)
    if cum==0:
        return 1
    edges[v] = cum
    return cum+1

dfs(0, 0)
powlis = [0]*N
for n in range(N):
    powlis[n] = pow(pow(2, n, mod), mod-2, mod)
ans = 0
for a, b, in AB:
    x = min(edges[a], edges[b])+1
    ans += (1-powlis[x])*(1-powlis[N-x])
    ans %= mod
ans = ans - N*pow(2, mod-2, mod)+1-pow(pow(2, N, mod), mod-2, mod)
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
AB = []
query = [[] for _ in range(N)]
mod = 10**9+7
import sys
sys.setrecursionlimit(10**6)
for _ in range(N-1):
    a, b = map(int, input().split())
    query[a-1].append(b-1)
    query[b-1].append(a-1)
    AB.append((a-1, b-1))

edges = [0]*N
def dfs(b, v):
    lis = []
    cum = 0
    for i in query[v]:
        if i==b:
            continue
        cum += dfs(v, i)
    if cum==0:
        return 1
    edges[v] = cum
    return cum+1

dfs(0, 0)
powlis = [0]*N
for n in range(N):
    powlis[n] = pow(pow(2, n, mod), mod-2, mod)
ans = 0
for a, b, in AB:
    x = min(edges[a], edges[b])+1
    ans += (1-powlis[x])*(1-powlis[N-x])
    ans %= mod
ans = ans - N*pow(2, mod-2, mod)+1-pow(pow(2, N, mod), mod-2, mod)
print(ans%mod)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
AB = []
query = [[] for _ in range(N)]
mod = 10**9+7
import sys
sys.setrecursionlimit(10**6)
for _ in range(N-1):
    a, b = map(int, input().split())
    query[a-1].append(b-1)
    query[b-1].append(a-1)
    AB.append((a-1, b-1))

edges = [0]*N
def dfs(b, v):
    lis = []
    cum = 0
    for i in query[v]:
        if i==b:
            continue
        cum += dfs(v, i)
    if cum==0:
        return 1
    edges[v] = cum
    return cum+1

dfs(0, 0)
ans = 0
for a, b, in AB:
    x = min(edges[a], edges[b])+1
    ans += (1-pow(pow(2, x, mod), mod-2, mod))*(1-pow(pow(2, N-x, mod), mod-2, mod))
    ans %= mod
ans = ans - N*pow(2, mod-2, mod)+1-pow(pow(2, N, mod), mod-2, mod)
print(ans%mod)

Submission status: Time Limit Exceeded

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

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

    cs = [1] * N
    def dfs(v,p=-1):
        ret = 1
        for to in es[v]:
            if to==p: continue
            ret += dfs(to,v)
        cs[v] = ret
        return ret
    dfs(0)
    ans = 0
    for i in range(N):
        if len(es[i]) == 1: continue
        ans += pow(2,N-1,MOD) - 1
        c = 0
        for to in es[i]:
            if cs[to] > cs[i]: continue
            c += cs[to]
            ans -= pow(2,cs[to],MOD) - 1
        ans -= pow(2,N-c-1,MOD) - 1

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

Submission status: Time Limit Exceeded

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

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

cs = [1] * N
def dfs(v,p=-1):
    ret = 1
    for to in es[v]:
        if to==p: continue
        ret += dfs(to,v)
    cs[v] = ret
    return ret
dfs(0)
ans = 0
for i in range(N):
    if len(es[i]) == 1: continue
    ans += pow(2,N-1,MOD) - 1
    c = 0
    for to in es[i]:
        if cs[to] > cs[i]: continue
        c += cs[to]
        ans -= pow(2,cs[to],MOD) - 1
    ans -= pow(2,N-c-1,MOD) - 1

ans *= pow(pow(2,N,MOD), MOD-2, MOD)
print(ans%MOD)

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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

	#DFS
	W = [1] * N
	Wlist = []
	visit = [0] * N
	visit[0] = 1
	DFS(G, W, Wlist, visit, 0)
	# print(W)
	# print(Wlist)

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

	for i in range(N):
		ans_up -= pow(2, N - W[i], con) - 1
		ans_up %= con

	# print(ans_up)

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

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

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

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

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

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

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

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

class power(object):
	def __init__(self, con):
		self.power = [0] * 19
		self.power[0] = 2
		for i in range(1, 19):
			self.power[i] = (self.power[i - 1] ** 2) % con

	def calc(self, M, con):
		ans = 1
		for i in range(19):
			if M & 1 == 1:
				ans = (ans * self.power[i]) % con
			M = M >> 1
			if M == 0:
				break

		return ans

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

	#DFS
	W = [1] * N
	Wlist = []
	visit = [0] * N
	visit[0] = 1
	DFS(G, W, Wlist, visit, 0)
	# print(W)
	# print(Wlist)
	for i in range(N):
		Wlist.append(N - W[i])

	P = power(con)
	# print(Wlist)
	pow2 = P.calc(N - 1, con)
	# print(pow2)
	# pow2 = pow(2, N - 1, con)
	# print(pow2)
	ans_up = N * (pow2 - 1)
	for i in Wlist:
		ans_up -= P.calc(i, con) - 1
		# ans_up -= pow(2, i, con) - 1
		ans_up %= con

	# print(ans_up)

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

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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

	#DFS
	W = [1] * N
	Wlist = []
	visit = [0] * N
	visit[0] = 1
	DFS(G, W, Wlist, visit, 0)
	# print(W)
	# print(Wlist)
	for i in range(N):
		Wlist += [N - W[i]]
		# Wlist.append(N - W[i])

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

	# print(ans_up)

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

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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

	#DFS
	W = [1] * N
	Wlist = []
	visit = [False] * N
	visit[0] = True
	DFS(G, W, Wlist, visit, 0)
	# print(W)
	# print(Wlist)
	for i in range(N):
		Wlist.append(N - W[i])

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

	# print(ans_up)

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

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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

	#DFS
	W = [1] * N
	Wlist = []
	visit = [0] * N
	visit[0] = 1
	DFS(G, W, Wlist, visit, 0)
	# print(W)
	# print(Wlist)
	for i in range(N):
		Wlist.append(N - W[i])

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

	# print(ans_up)

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

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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

	#DFS
	W = [1] * N
	Wlist = []
	visit = ["No"] * N
	visit[0] = "Yes"
	DFS(G, W, Wlist, visit, 0)
	# print(W)
	# print(Wlist)
	for i in range(N):
		Wlist.append(N - W[i])

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

	# print(ans_up)

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

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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

	#DFS
	W = [1] * N
	Wlist = [[] for i in range(N)]
	visit = ["No"] * N
	visit[0] = "Yes"
	DFS(G, W, Wlist, visit, 0)
	# print(W)
	# print(Wlist)
	for i in range(N):
		Wlist[i].append(N - W[i])

	# print(Wlist)
	pow2 = pow(2, N - 1, con)
	ans_up = N * (pow2 - 1)
	for i in range(N):
		for j in Wlist[i]:
			ans_up -= pow(2, j, con) - 1
			ans_up %= con

	# print(ans_up)

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

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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

	#DFS
	W = [1] * N
	Wlist = [[0] for i in range(N)]
	visit = ["No"] * N
	visit[0] = "Yes"
	DFS(G, W, Wlist, visit, 0)
	# print(W)
	# print(Wlist)
	for i in range(N):
		Wlist[i].append(N - W[i])

	# print(Wlist)
	ans_up = 0
	pow2 = pow(2, N - 1, con)
	for i in range(N):
		ans_up += pow2 - 1
		for j in Wlist[i]:
			ans_up -= pow(2, j, con) - 1
			ans_up %= con

	# print(ans_up)

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

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

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

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

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

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

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

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

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

	#DFS
	W = [1] * N
	Wlist = [[0] for i in range(N)]
	visit = ["No"] * N
	visit[0] = "Yes"
	DFS(G, W, Wlist, visit, 0)
	# print(W)
	# print(Wlist)
	for i in range(N):
		Wlist[i].append(N - 1 - sum(Wlist[i]))

	# print(Wlist)
	ans_up = 0
	pow2 = pow(2, N - 1, con)
	for i in range(N):
		ans_up += pow2 - 1
		for j in Wlist[i]:
			ans_up -= pow(2, j, con) - 1

	# print(ans_up)

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

if __name__ == '__main__':
	main()