Submission #18541179


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

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

Submission Time
Task P - うなぎ
User shotoyoo
Language PyPy3 (7.3.0)
Score 6
Code Size 1785 Byte
Status AC
Exec Time 402 ms
Memory 80792 KB

Judge Result

Set Name All
Score / Max Score 6 / 6
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 164 ms 70196 KB
01 AC 87 ms 68904 KB
02 AC 376 ms 79576 KB
03 AC 402 ms 80120 KB
04 AC 389 ms 79764 KB
05 AC 386 ms 80636 KB
06 AC 375 ms 80792 KB
90 AC 56 ms 62224 KB
91 AC 56 ms 62512 KB