解题思路

依赖无环且每件用品只有至多一个前置对象，因此构成森林。将没有前置对象的用品作为各棵树的根，按先访问父亲、再访问子树的顺序得到数组 $order$ 。记录 $end[u]$ 为编号 $u$ 的整棵子树之后的位置。
在这种先序排列中，每棵子树对应连续区间。若不选用品 $u$ ，它的后代都不能选，可以直接跳至 $end[u]$ ；若选择它，则扣除重量并进入下一个位置，其孩子此时已经具备前置条件。
设 $dp[t][b]$ 表示从先序位置 $t$ 继续考虑、剩余容量为 $b$ 的最大收益。此状态只在此前路径已经选好所需祖先时使用。令 $u=order[t]$ ，不选时为 $dp[end[u]][b]$ ；容量足够时，选中得到 $gain[u]+dp[t+1][b-cost[u]]$ ，取二者最大值。
边界 $dp[m][b]=0$ ，按位置从后向前计算，答案为 $dp[0][cap]$ 。任意合法集合对当前用品必有选或不选两种情况，上述转移覆盖两者且不产生非法依赖，所以得到最优值。
Python使用整数数组保存各行，避免普通Python整数表占用过多内存；显式栈保证长链输入不会触发递归深度限制。

复杂度分析

准备搬家的小王有一个承重上限为 $cap$ 的箱子，打算从 $m$ 件随身用品中选出若干件带走。每件用品记录两项信息：

某些用品要搭配其他用品使用：若选了编号 $p$ 的用品，就必须同时选上 $parent_p$ 指定的用品。每件用品最多指定一个前置对象，同一件用品也至多装入一次。请在重量不超过箱子承重的前提下，使取得的价值之和尽可能高。

首行按顺序给出 $cap,m$ 。

接着 $m$ 行，每行是 $cost_p,gain_p$ ，按编号从 $0$ 至 $m-1$ 描述各件用品。

末行包含 $m$ 个整数，组成数组 $parent$ 。当 $parent_p=-1$ 时，该件没有前置对象；否则必须先选编号为 $parent_p$ 的那件。

打印所能取得的最高价值；可以不选任何用品。

范围： $1\le m\le1000$ ， $1\le cap\le10^4$ ， $1\le cost_p\le cap$ ， $1\le gain_p\le10^4$ 。每个 $parent_p$ 为 $-1$ 或 $[0,m-1]$ 内与 $p$ 不同的编号。

依赖允许跨越多层，但保证不存在环。若某件被选中，它的直接前置对象及继续向上的所有前置对象都必须选中。这一无环条件用于补全图片中未明确的输入保证。

输入

输出

说明

选择编号 $2,3$ 的价值为 $10$ ；选择 $0,1$ 的价值为 $11$ 。选择 $0,2$ 恰重 $7$ ，取得价值 $13$ ，为唯一最优集合。

输入

输出

说明

编号 $1$ 若入箱，就必须同时带上编号 $0$ ，总重 $4$ 超限，因此只能选择编号 $0$ 或不选，最优价值为 $2$ 。

选择提交后点击「开始AI分析」