| 问题描述 |
|---|
Agent 在解决一个复杂任务时，会生成若干棵“思维树”。每个节点表示一段可以展开的推理。 第 $$i$$ 个推理节点有三个属性： - 父节点 $$p_i$$ - 展开这个节点需要消耗 $$c_i$$ 个 token - 展开后可以获得 $$v_i$$ 点收益 如果 $$p_i = 0$$，说明第 $$i$$ 个节点是一个顶层推理节点，可以直接展开；否则，只有在它的父节点 $$p_i$$ 已经被展开后，节点 $$i$$ 才能被展开。 Agent 的上下文预算最多为 $$M$$ 个 token。你需要帮助 Agent 选择若干个推理节点展开，使得： 1. 被选择节点的总 token 消耗不超过 $$M$$； 2. 若选择了某个节点，则它的所有祖先节点也必须被选择； 3. 获得的总收益尽可能大。 请输出 Agent 最多可以获得多少收益。 |
| 输入描述 |
第一行两个整数 $$N$$ 和 $$M$$，表示推理节点数量和 token 预算。（$$1 \le N, M \le 2000$$） 接下来 $$N$$ 行，第 $$i$$ 行包含三个整数 $$p_i, c_i, v_i$$，分别表示第 $$i$$ 个节点的父节点、token 消耗和收益。（$$0 \le p_i < i$$,$$1 \le c_i \le M$$,$$1 \le v_i \le 10^9$$） 保证 $$0 \le p_i < i$$，因此父节点一定比子节点先出现。 |
| 输出描述 |
输出一行一个整数，表示在预算内可以获得的最大总收益。 |
| 样例输入复制样例 |
4 5 0 3 10 1 3 100 0 3 4 3 2 5 |
| 样例输出 |
10 |
| 提示说明 |
节点 $$2$$ 的收益很高，但要选择节点 $$2$$，必须同时选择它的父节点 $$1$$，总消耗为 $$3 + 3 = 6$$，超过预算 $$5$$。 如果选择节点 $$3, 4$$，总消耗为 $$3 + 2 = 5$$，收益为 $$4 + 5 = 9$$。 因此最优方案是只选择节点 $$1$$，收益为 $$10$$。 |
| 相关 |