結果

問題 No.3283 Labyrinth and Friends
コンテスト
ユーザー kidodesu
提出日時 2025-09-26 22:21:13
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 289 ms / 2,000 ms
コード長 1,180 bytes
コンパイル時間 405 ms
コンパイル使用メモリ 82,652 KB
実行使用メモリ 80,252 KB
最終ジャッジ日時 2025-09-26 22:21:20
合計ジャッジ時間 6,855 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

n, x = map(int, input().split())
P = [0] + list(map(int, input().split()))
P = [P[i]-1 for i in range(n)]
V = [[] for _ in range(n)]
for i in range(1, n):
    V[P[i]].append(i)
CS = [(0, 0)] + [tuple(map(int, input().split())) for _ in range(n-1)]
from collections import deque
dq = deque([0])
D = [-1] * n; D[0] = 0
DD = [[] for _ in range(n+1)]
while dq:
    now = dq.popleft()
    DD[D[now]].append(now)
    for nxt in V[now]:
        D[nxt] = D[now] + 1
        dq.append(nxt)
dp = [[0] for _ in range(n)]

inf = float("INF")
def merge(A0, A1):
    a0 = len(A0)-1
    a1 = len(A1)-1
    ndp = [inf] * (a0 + a1 + 1)
    for now in range(a0+1):
        for nxt in range(a1+1):
            ndp[now+nxt] = min(ndp[now+nxt], A0[now]+A1[nxt])
    return ndp

for d in range(n, -1, -1):
    for now in DD[d]:
        for nxt in V[now]:
            dp[now] = merge(dp[now], dp[nxt])[:]
        c, s = CS[now]
        ndp = [inf] * (s + len(dp[now]))
        for i in range(len(dp[now])):
            ndp[i+s] = dp[now][i]+c
        #print(ndp)
        ndp[0] = 0
        dp[now] = ndp[:]

#print(dp[0])

ans = inf
for i in range(x, len(dp[0])):
    ans = min(ans, dp[0][i])
print(ans)
0