Submission #18541939


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]] * 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

Submission Time
Task N - 木
User shotoyoo
Language PyPy3 (7.3.0)
Score 0
Code Size 1938 Byte
Status TLE
Exec Time 2209 ms
Memory 102692 KB

Judge Result

Set Name All
Score / Max Score 0 / 5
Status
AC × 8
TLE × 1
Set Name Test Cases
All 00, 01, 02, 03, 04, 05, 06, 90, 91
Case Name Status Exec Time Memory
00 TLE 2209 ms 102692 KB
01 AC 113 ms 76636 KB
02 AC 130 ms 83004 KB
03 AC 127 ms 82064 KB
04 AC 130 ms 81612 KB
05 AC 128 ms 81536 KB
06 AC 128 ms 82624 KB
90 AC 58 ms 62132 KB
91 AC 55 ms 62284 KB