Submission #18541179

---

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")

n,k = list(map(int, input().split()))
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)
dp0 = [[0]*n for _ in range(k+2)]
dp1 = [[0]*n for _ in range(k+2)]
dp2 = [[0]*n for _ in range(k+2)]
M = 10**9+7
def ss(i,u):
    return (dp0[i][u] + dp1[i][u] + dp2[i][u])%M
def sub(u,v):
#     print(u,v,dp0)
    ndp0 = [0]*(k+2)
    ndp1 = [0]*(k+2)
    ndp2 = [0]*(k+2)
    for i in range(k+1):
        for j in range(k+1-i+1):
            su = ss(i,u)
            sv = ss(j,v)
            ndp2[i+j] += dp2[i][u] * sv
            ndp2[i+j] += dp1[i][u] * dp0[j][v]
            if i+j>=1:
                ndp2[i+j-1] += dp1[i][u] * dp1[j][v]
            ndp1[i+j] += dp1[i][u] * sv + dp0[i][u]*(dp1[j][v])
            if i+j+1<len(dp1):
                ndp1[i+j+1] += dp0[i][u]*dp0[j][v]
#                 ndp2[i+j+1] += dp0[i][u]*dp0[j][v]
            ndp0[i+j] += dp0[i][u] * sv
    for j in range(k+2):
        dp0[j][u] = ndp0[j]%M
        dp1[j][u] = ndp1[j]%M
        dp2[j][u] = ndp2[j]%M
# 深さ優先探索 (巻き戻しあり) dfs
s = [(0, -1)]
while s:
    u,prv = s.pop()
    if u<0:
        # 返るときの処理
        u = ~u
        dp0[0][u] = 1
        if True:
            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 = ss(k,0)%M
print(ans%M)

Submission Info

Judge Result