Submission #18541957


Source Code Expand

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

### 木の読み込み yomikomi
n = int(input())
ns = [[] for _ in range(n)]
for _ in range(n-1):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].append(v)
    ns[v].append(u)
dp = [[0]*n for _ in range(n)]
size = [0]*n
for u in range(n):
    dp[u][1] = 1
M = 10**9+7
# 深さ優先探索 (巻き戻しあり) dfs
N = n+20 # 必要なテーブルサイズ
g1 = [0] * (N+1) # 元テーブル
g2 = [0] * (N+1) #逆元テーブル
inverse = [0] * (N+1) #逆元テーブル計算用テーブル
g1[0] = g1[1] = g2[0] = g2[1] = 1
inverse[0], inverse[1] = [0, 1] 
for i in range( 2, N + 1 ):
    g1[i] = ( g1[i-1] * i ) % M 
    inverse[i] = ( -inverse[M % i] * (M//i) ) % M # ai+b==0 mod M <=> i==-b*a^(-1) <=> i^(-1)==-b^(-1)*aより
    g2[i] = (g2[i-1] * inverse[i]) % M 
s = [(0, -1)]
def sub(u,v):
    ndp = [0]*n
    ndp[1] = (g1[size[u]+size[v]] * g2[size[u]] * g2[size[v]] % M) * (dp[u][1] * dp[v][1] % M)
    ndp[1] %= M
    for i in range(1,size[u]+1):
        ndp[i] += (dp[u][i] * dp[v][1] % M) * ((g1[size[u]+size[v]+1-i] * g2[size[v]+1] % M) * g2[size[u]-i] % M)
        ndp[i] %= M
    cum = 0
    for i in range(1,size[v]+1):
        cum += dp[v][i]
        cum %= M
        ndp[i+1] += (cum * dp[u][1] % M) * ((g1[size[u]+size[v]-i] * g2[size[u]] % M) * g2[size[v]-i] % M)
        ndp[i+1] %= M
    dp[u] = ndp
    size[u] = size[u] + size[v] + 1
#     print(ndp)
        
while s:
    u,prv = s.pop()
    if u<0:
        # 返るときの処理
        u = ~u
        for v in ns[u]:
            if v==prv:
                continue
            sub(u,v)
    else:
        s.append((~u,prv))
        for v in ns[u]:
            # 進むときの処理
            if v==prv:
                continue
            s.append((v,u))
ans = sum(dp[0])%M
print(ans%M)

Submission Info

Submission Time
Task N - 木
User shotoyoo
Language PyPy3 (7.3.0)
Score 5
Code Size 1997 Byte
Status AC
Exec Time 130 ms
Memory 82488 KB

Judge Result

Set Name All
Score / Max Score 5 / 5
Status
AC × 9
Set Name Test Cases
All 00, 01, 02, 03, 04, 05, 06, 90, 91
Case Name Status Exec Time Memory
00 AC 116 ms 80840 KB
01 AC 94 ms 76684 KB
02 AC 130 ms 82084 KB
03 AC 126 ms 81892 KB
04 AC 130 ms 81872 KB
05 AC 130 ms 82488 KB
06 AC 122 ms 81768 KB
90 AC 56 ms 62192 KB
91 AC 54 ms 62292 KB