A5965 | 「THUPC 2024 初赛」采矿

你是一个矿坑老板。

你的矿坑是二叉树形结构，有 $n$ 个节点。$1$ 号点为地面，对于所有的 $2\le i\le n$，$i$ 号节点与更浅层的 $f_i$ 号节点通过通道相连，其中 $f_i<i$，且相同的 $f_i$ 最多出现两次。矿坑的不同节点的产量和开采难度均不相同。对于 $i$ 号节点 $(2\le i\le n)$，如果派一个机器人开采，一单位时间内能有 $r_i$ 的产出；如果派一个人类开采，一单位时间内能有 $p_i$ 的产出。地面没有产出。

你有一个机器人，初始位于 $s$ 号节点。你的矿坑里初始没有人类工人。

所有通道与节点都十分狭窄，每个节点都只能容下一名工人（工人包括人类和机器人），每个通道也只能恰好容一名工人通过。在移动的任何时刻，只能有最多一名工人在通道中，其余工人都必须在节点上。

你现在有 $q$ 条计划需要按顺序执行。每个计划分为准备、执行、调整、开采四个阶段。

在准备阶段，人类可以在满足上述移动规则的前提下任意移动，但不能进入或离开矿坑（矿坑内的工人到达 $1$ 号节点不算离开矿坑），因为你在看着他们；移动的顺序和次数均没有限制。机器人不能移动。

在执行阶段，不同计划需要做的事情可能不同，共分为 $4$ 种：

1. 机器人只能沿通道向**更浅**的方向移动，且至少需要经过一条通道。人类不能移动。
2. 机器人只能沿通道向**更深**的方向移动，且至少需要经过一条通道。人类不能移动。
3. 使一名人类从 $1$ 号节点进入矿坑（这意味着该阶段开始时 $1$ 号节点上必须没有工人）。除此之外所有工人都不能移动。
4. 使一名人类从 $1$ 号节点移出矿坑（这意味着该阶段开始时 $1$ 号节点上必须有一名人类）。除此之外所有工人都不能移动。

在调整阶段，限制与准备阶段相同。人类可以在满足上述移动规则的前提下任意移动，但不能进入或离开矿坑；移动的顺序和次数均没有限制。机器人不能移动。

在开采阶段，所有的工人会采一单位时间的矿。所有有工人的非地面节点会根据位于该节点的工人种类计算产出。没有工人的节点没有产出。该计划的产出为所有节点的产出之和。

问按顺序执行完所有计划之后，你所有计划的产出之和最多可以达到多少。

第一行三个正整数 $n,q,s$。

第二行 $n-1$ 个整数，其中第 $i$（$1\le i<n$，下同）个表示 $f_{i+1}$。

第三行 $n-1$ 个整数，其中第 $i$ 个表示 $r_{i+1}$。

第四行 $n-1$ 个整数，其中第 $i$ 个表示 $p_{i+1}$。

接下来 $q$ 行，每行一个整数表示计划的种类，其中第 $i$ 个整数表示第 $i$ 条计划：

- 1 表示第一种计划：将机器人向更浅的方向移动；
- 2 表示第二种计划：将机器人向更深的方向移动；
- 3 表示第三种计划：将一名人类从 $1$ 号节点送入矿坑；
- 4 表示第四种计划：将一名人类从 $1$ 号节点移出矿坑。

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