ABC 149 F Surrounded Nodes【Python】

問題はこちら。

import sys
sys.setrecursionlimit(10**9)

MOD = 10**9 + 7

N = int(input())
conn = [[] for _ in range(N)]
for _ in range(N - 1):
   A, B = map(int, input().split())
   A -= 1; B -= 1
   conn[A].append(B)
   conn[B].append(A)
   
checked = [False]*N
size = [1]*N
def dfs(x):
   if checked[x]:
       return
   checked[x] = True
   for y in conn[x]:
       if not checked[y]:
           dfs(y)
           size[x] += size[y]
dfs(0)
ans = 0
for i in range(1, N):
   x = size[i]
   ans += (pow(2, x, MOD) - 1) * (pow(2, N - x, MOD) - 1)
ans += pow(2, N, MOD) - 1 - N * pow(2, N - 1, MOD)
ans *= pow(pow(2, N, MOD), MOD - 2, MOD)
ans %= MOD

print(ans)