[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$ 号节点上必须有一名人类）。除此之外所有工人都不能移动。 在调整阶段，限制与准备阶段相同。人类可以在满足上述移动规则的前提下任意移动，但不能进入或离开矿坑；移动的顺序和次数均没有限制。机器人不能移动。 在开采阶段，所有的工人会采一单位时间的矿。所有有工人的非地面节点会根据位于该节点的工人种类计算产出。没有工人的节点没有产出。该计划的产出为所有节点的产出之和。 问按顺序执行完所有计划之后，你所有计划的产出之和最多可以达到多少。 ## Input 第一行三个正整数 $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$ 号节点移出矿坑。 ## Output 如果无论如何你都无法完成你的计划，输出一行 `No solution.`。否则输出一行一个整数，表示你的产出之和的最大值。 [samples] ## Background _“我已经买不起第二个机器人了。”_ _“那就雇点人来凑数吧。注意别给死里头。”_ ## Note ### 样例 \#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 地址。