Background

"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."

Problem Description

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<i$, and each same value of $f_i$ appears at most twice. Different nodes in the mine have different productivity and mining difficulty. For node $i$ $(2\le i\le n)$, if you assign a robot to mine there, it produces $r_i$ output per unit time; if you assign a human to mine there, it produces $p_i$ output per unit time. The ground produces no output.

You have one robot, initially located at node $s$. Initially, there are no human workers in your mine.

All tunnels and nodes are very narrow. Each node can hold only one worker (workers include both humans and the robot). Each tunnel can also allow exactly one worker to pass through. At any moment during movement, there can be at most one worker in a tunnel; all other workers must stay on nodes.

You now have $q$ plans that must be executed in order. Each plan consists of four phases: preparation, execution, adjustment, and mining.

In the preparation phase, humans may move arbitrarily as long as the above movement rules are satisfied, but they cannot enter or leave the mine (a worker in the mine reaching node $1$ is not considered leaving the mine), because you are watching them. There is no limit on the order or number of moves. The robot cannot move.

In the execution phase, different plans require different actions. There are $4$ types in total:

1. The robot may only move along tunnels toward a shallower direction, and it must pass through at least one tunnel. Humans cannot move.
2. The robot may only move along tunnels toward a deeper direction, and it must pass through at least one tunnel. Humans cannot move.
3. Make one human enter the mine from node $1$ (this means that at the start of this phase, there must be no worker on node $1$). Besides this, no worker may move.
4. Make one human leave the mine via node $1$ (this means that at the start of this phase, there must be a human on node $1$). Besides this, no worker may move.

In the adjustment phase, the restrictions are the same as in the preparation phase. Humans may move arbitrarily as long as the movement rules are satisfied, but they cannot enter or leave the mine. There is no limit on the order or number of moves. The robot cannot move.

In the mining phase, all workers mine for one unit of time. Every non-ground node that has a worker produces output according to the type of worker on that node. Nodes without workers produce no output. The output of this plan is the sum of the outputs of all nodes.

Compute the maximum possible total output summed over all plans after executing all plans in order.

Input Format

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<n,\text{ same below})$ denotes $f_{i+1}$.

The third line contains $n-1$ integers, where the $i$-th one denotes $r_{i+1}$.

The fourth line contains $n-1$ integers, where the $i$-th one denotes $p_{i+1}$.

The next $q$ lines each contain one integer indicating the type of a plan, where the $i$-th integer denotes the $i$-th plan:

• 1 means the first type: move the robot in a shallower direction;
• 2 means the second type: move the robot in a deeper direction;
• 3 means the third type: send one human into the mine from node $1$;
• 4 means the fourth type: move one human out of the mine via node $1$.

Output Format

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.

5 6 4
1 1 3 3
15 9 7 1
4 2 8 6
3
3
1
2
2
4

91

Hint

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).

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