P9967 [THUPC 2024 Preliminary] Mining.

_"I can't afford a second robot anymore."_ _"Then hire some people to make up the numbers. Just don't get them killed in there."_

You are the owner of a mine. Your mine has a binary-tree structure with $n$ nodes. Node $1$ is the ground. For all $2\le i\le n$, node $i$ is connected by a tunnel to a shallower node $f_i$, where $f_i

The first line contains three positive integers $n,q,s$. The second line contains $n-1$ integers, where the $i$-th one $(1\le i

If it is impossible to complete your plans no matter what, output one line `No solution.`. Otherwise, output one line with one integer, the maximum total output.

### Sample \#1 Explanation One optimal solution is as follows (some phases with no movement are omitted): Adjustment phase of the first plan: move the human just sent into node $1$ twice to node $5$. Mining phase of the first plan: the robot output is $7$, and the human output is $6$. Adjustment phase of the second plan: move the human just sent into node $1$ to node $2$. Mining phase of the second plan: the robot output is $7$, and the human output is $4+6=10$. Execution phase of the third plan: move the robot to node $1$. Adjustment phase of the third plan: move one human from node $5$ to node $4$. Mining phase of the third plan: the robot output is $0$, and the human output is $4+8=12$. Preparation phase of the fourth plan: move one human from node $4$ to node $5$. Execution phase of the fourth plan: move the robot to node $3$. Mining phase of the fourth plan: the robot output is $9$, and the human output is $4+6=10$. Execution phase of the fifth plan: move the robot to node $4$. Mining phase of the fifth plan: the robot output is $7$, and the human output is $4+6=10$. Preparation phase of the sixth plan: move one human from node $2$ to node $1$. Mining phase of the sixth plan: the robot output is $7$, and the human output is $6$. The total output is $7+6+7+10+0+12+9+10+7+10+7+6=91$. ### Subtasks It is guaranteed that $2\le n\le 301$, $1\le q \le 600$, and $1\le s\le n$. It is guaranteed that $1\le f_i < i$ and $0\le r_i,p_i \le 10^9$. It is guaranteed that each same value of $f_i$ appears at most twice. ### Problem Usage Agreement From the THUPC2024 (Tsinghua University Programming Contest and Collegiate Invitational Contest 2024) preliminary round. In the following, "this repository" refers to the official THUPC2024 preliminary repository ([https://github.com/ckw20/thupc2024_pre_public](https://github.com/ckw20/thupc2024_pre_public)). 1. Any organization or individual may use or redistribute the problems in this repository for free. 2. When using the problems in this repository, any organization or individual should do so free of charge and publicly. It is strictly forbidden to use these problems for profit or to add special permissions to these problems. 3. If possible, when using the problems in this repository, please also provide how to obtain resources such as the testdata, reference solution, and editorial. Otherwise, please attach the GitHub link of this repository. Translated by ChatGPT 5