結果

問題 No.3283 Labyrinth and Friends
ユーザー hirayuu_yc
提出日時 2025-09-20 23:26:49
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 277 ms / 2,000 ms
コード長 2,968 bytes
コンパイル時間 598 ms
コンパイル使用メモリ 82,840 KB
実行使用メモリ 80,640 KB
最終ジャッジ日時 2025-09-25 21:03:19
合計ジャッジ時間 7,851 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
sys.setrecursionlimit(10000)
INF = 10**30

def solve():
    data = sys.stdin.read().strip().split()
    if not data:
        return
    it = iter(data)
    N = int(next(it))
    X = int(next(it))
    if N == 1:
        print(0)
        return
    parents = [0]*(N+1)
    for i in range(2, N+1):
        parents[i] = int(next(it))
    c = [0]*(N+1)
    s = [0]*(N+1)
    for i in range(2, N+1):
        c[i] = int(next(it))
        s[i] = int(next(it))

    # children list
    children = [[] for _ in range(N+1)]
    for i in range(2, N+1):
        children[parents[i]].append(i)

    # DFS returns dp array length X+1: dp[k] = min cost to obtain exactly k status from this node's descendants
    # assuming this node itself is already unlocked. Index X means ">= X".
    def dfs(v):
        # start: from no children, dp[0]=0
        dp = [INF] * (X+1)
        dp[0] = 0
        cur_max = 0  # maximum k reachable currently (<= X)

        for u in children[v]:
            child_dp = dfs(u)  # child_dp[t_sub] = cost to get t_sub from u's descendants when u is unlocked
            # build opt array for this child: opt[t] = min cost to get total t from this child-branch
            # option t=0: not unlocking child => cost 0
            opt = [INF] * (X+1)
            opt[0] = 0
            # find child's possible max t_sub (where child_dp[t_sub] < INF)
            child_max_sub = 0
            for t_sub in range(X+1):
                if child_dp[t_sub] < INF:
                    child_max_sub = t_sub
            # we can choose to unlock child: total status = s[u] + t_sub
            for t_sub in range(child_max_sub+1):
                cost_sub = child_dp[t_sub]
                if cost_sub >= INF:
                    continue
                tot = s[u] + t_sub
                if tot > X:
                    tot = X
                # cost includes unlocking child
                opt[tot] = min(opt[tot], c[u] + cost_sub)

            # compute child_possible_max (max j with opt[j] < INF)
            child_max = 0
            for j in range(X+1):
                if opt[j] < INF:
                    child_max = j

            # merge dp and opt into new_dp, bounds are cur_max and child_max
            new_max = min(X, cur_max + child_max)
            new_dp = [INF] * (X+1)
            for i_k in range(cur_max+1):
                ci = dp[i_k]
                if ci >= INF:
                    continue
                for j_k in range(child_max+1):
                    cj = opt[j_k]
                    if cj >= INF:
                        continue
                    nk = i_k + j_k
                    if nk > X:
                        nk = X
                    val = ci + cj
                    if val < new_dp[nk]:
                        new_dp[nk] = val
            dp = new_dp
            cur_max = new_max

        return dp

    root_dp = dfs(1)
    ans = root_dp[X]
    print(ans)

if __name__ == "__main__":
    solve()
0