题目背景

“我已经买不起第二个机器人了。”

“那就雇点人来凑数吧。注意别给死里头。”

题目描述

你是一个矿坑老板。

你的矿坑是二叉树形结构，有 $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.。否则输出一行一个整数，表示你的产出之和的最大值。

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

91

提示

样例 #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）

1. 任何单位或个人都可以免费使用或转载本仓库的题目；

2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；

3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库的 github 地址。