P9967 [THUPC 2024 初赛] 采矿

_“我已经买不起第二个机器人了。”_ _“那就雇点人来凑数吧。注意别给死里头。”_

你是一个矿坑老板。 你的矿坑是二叉树形结构，有 $n$ 个节点。$1$ 号点为地面，对于所有的 $2\le i\le n$，$i$ 号节点与更浅层的 $f_i$ 号节点通过通道相连，其中 $f_i

第一行三个正整数 $n,q,s$。 第二行 $n-1$ 个整数，其中第 $i$（$1\le i

如果无论如何你都无法完成你的计划，输出一行 `No solution.`。否则输出一行一个整数，表示你的产出之和的最大值。

### 样例 \#1 解释 一个最优解如下：（一些没有移动的阶段略过不提） 第一个计划的调整阶段：将刚送入 $1$ 号点的人类移动两次到 $5$ 号点。 第一个计划的开采阶段：机器人产出为 $7$，人类产出为 $6$。 第二个计划的调整阶段：将刚送入 $1$ 号点的人类移动到 $2$ 号点。 第二个计划的开采阶段：机器人产出为 $7$，人类产出为 $4+6=10$。 第三个计划的执行阶段：将机器人移动至 $1$ 号点。 第三个计划的调整阶段：将一名人类从 $5$ 号点移动至 $4$ 号点。 第三个计划的开采阶段：机器人产出为 $0$，人类产出为 $4+8=12$。 第四个计划的准备阶段：将一名人类从 $4$ 号点移动至 $5$ 号点。 第四个计划的执行阶段：将机器人移动至 $3$ 号点。 第四个计划的开采阶段：机器人产出为 $9$，人类产出为 $4+6=10$。 第五个计划的执行阶段：将机器人移动至 $4$ 号点。 第五个计划的开采阶段：机器人产出为 $7$，人类产出为 $4+6=10$。 第六个计划的准备阶段：将一名人类从 $2$ 号点移动至 $1$ 号点。 第六个计划的开采阶段：机器人产出为 $7$，人类产出为 $6$。 总的产出为 $7+6+7+10+0+12+9+10+7+10+7+6=91$。 ### 子任务 保证 $2\le n\le 301$，$1\le q \le 600$，$1\le s\le n$。 保证 $1\le f_i < i$，$0\le r_i,p_i \le 10^9$。 保证相同的 $f_i$ 最多出现两次。 ### 题目使用协议 来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）初赛。 以下『本仓库』皆指 THUPC2024 初赛 官方仓库（[https://github.com/ckw20/thupc2024_pre_public](https://github.com/ckw20/thupc2024_pre_public)） 1. 任何单位或个人都可以免费使用或转载本仓库的题目； 2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限； 3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库的 github 地址。