Submission #18541939

---

Source Code Expand

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]] * dp[u][1] * dp[v][1]
    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] * g2[size[u]-i] % M)
        ndp[i] %= M
    cum = 0
    for i in range(1,size[v]+1):
        cum += dp[v][i]
        ndp[i+1] += (cum * dp[u][1] % M) * (g1[size[u]+size[v]-i] * g2[size[u]] * 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

Judge Result