{"raw_statement":[{"iden":"background","content":"_“我已经买不起第二个机器人了。”_\n\n_“那就雇点人来凑数吧。注意别给死里头。”_"},{"iden":"statement","content":"你是一个矿坑老板。\n\n你的矿坑是二叉树形结构，有 $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$ 的产出。地面没有产出。\n\n你有一个机器人，初始位于 $s$ 号节点。你的矿坑里初始没有人类工人。\n\n所有通道与节点都十分狭窄，每个节点都只能容下一名工人（工人包括人类和机器人），每个通道也只能恰好容一名工人通过。在移动的任何时刻，只能有最多一名工人在通道中，其余工人都必须在节点上。\n\n你现在有 $q$ 条计划需要按顺序执行。每个计划分为准备、执行、调整、开采四个阶段。\n\n在准备阶段，人类可以在满足上述移动规则的前提下任意移动，但不能进入或离开矿坑（矿坑内的工人到达 $1$ 号节点不算离开矿坑），因为你在看着他们；移动的顺序和次数均没有限制。机器人不能移动。\n\n在执行阶段，不同计划需要做的事情可能不同，共分为 $4$ 种：\n\n1. 机器人只能沿通道向**更浅**的方向移动，且至少需要经过一条通道。人类不能移动。\n2. 机器人只能沿通道向**更深**的方向移动，且至少需要经过一条通道。人类不能移动。\n3. 使一名人类从 $1$ 号节点进入矿坑（这意味着该阶段开始时 $1$ 号节点上必须没有工人）。除此之外所有工人都不能移动。\n4. 使一名人类从 $1$ 号节点移出矿坑（这意味着该阶段开始时 $1$ 号节点上必须有一名人类）。除此之外所有工人都不能移动。\n\n在调整阶段，限制与准备阶段相同。人类可以在满足上述移动规则的前提下任意移动，但不能进入或离开矿坑；移动的顺序和次数均没有限制。机器人不能移动。\n\n在开采阶段，所有的工人会采一单位时间的矿。所有有工人的非地面节点会根据位于该节点的工人种类计算产出。没有工人的节点没有产出。该计划的产出为所有节点的产出之和。\n\n问按顺序执行完所有计划之后，你所有计划的产出之和最多可以达到多少。"},{"iden":"input","content":"第一行三个正整数 $n,q,s$。\n\n第二行 $n-1$ 个整数，其中第 $i$（$1\\le i<n$，下同）个表示 $f_{i+1}$。\n\n第三行 $n-1$ 个整数，其中第 $i$ 个表示 $r_{i+1}$。\n\n第四行 $n-1$ 个整数，其中第 $i$ 个表示 $p_{i+1}$。\n\n接下来 $q$ 行，每行一个整数表示计划的种类，其中第 $i$ 个整数表示第 $i$ 条计划：\n\n- `1` 表示第一种计划：将机器人向更浅的方向移动；\n- `2` 表示第二种计划：将机器人向更深的方向移动；\n- `3` 表示第三种计划：将一名人类从 $1$ 号节点送入矿坑；\n- `4` 表示第四种计划：将一名人类从 $1$ 号节点移出矿坑。"},{"iden":"output","content":"如果无论如何你都无法完成你的计划，输出一行 `No solution.`。否则输出一行一个整数，表示你的产出之和的最大值。"},{"iden":"note","content":"### 样例 \\#1 解释\n\n一个最优解如下：（一些没有移动的阶段略过不提）\n\n第一个计划的调整阶段：将刚送入 $1$ 号点的人类移动两次到 $5$ 号点。\n\n第一个计划的开采阶段：机器人产出为 $7$，人类产出为 $6$。\n\n第二个计划的调整阶段：将刚送入 $1$ 号点的人类移动到 $2$ 号点。\n\n第二个计划的开采阶段：机器人产出为 $7$，人类产出为 $4+6=10$。\n\n第三个计划的执行阶段：将机器人移动至 $1$ 号点。\n\n第三个计划的调整阶段：将一名人类从 $5$ 号点移动至 $4$ 号点。\n\n第三个计划的开采阶段：机器人产出为 $0$，人类产出为 $4+8=12$。\n\n第四个计划的准备阶段：将一名人类从 $4$ 号点移动至 $5$ 号点。\n\n第四个计划的执行阶段：将机器人移动至 $3$ 号点。\n\n第四个计划的开采阶段：机器人产出为 $9$，人类产出为 $4+6=10$。\n\n第五个计划的执行阶段：将机器人移动至 $4$ 号点。\n\n第五个计划的开采阶段：机器人产出为 $7$，人类产出为 $4+6=10$。\n\n第六个计划的准备阶段：将一名人类从 $2$ 号点移动至 $1$ 号点。\n\n第六个计划的开采阶段：机器人产出为 $7$，人类产出为 $6$。\n\n总的产出为 $7+6+7+10+0+12+9+10+7+10+7+6=91$。\n\n### 子任务\n\n保证 $2\\le n\\le 301$，$1\\le q \\le 600$，$1\\le s\\le n$。\n\n保证 $1\\le f_i < i$，$0\\le r_i,p_i \\le 10^9$。\n\n保证相同的 $f_i$ 最多出现两次。\n\n### 题目使用协议\n\n来自 THUPC2024（2024年清华大学学生程序设计竞赛暨高校邀请赛）初赛。\n\n以下『本仓库』皆指 THUPC2024 初赛 官方仓库（[https://github.com/ckw20/thupc2024_pre_public](https://github.com/ckw20/thupc2024_pre_public)）\n\n1. 任何单位或个人都可以免费使用或转载本仓库的题目；\n\n2. 任何单位或个人在使用本仓库题目时，应做到无偿、公开，严禁使用这些题目盈利或给这些题目添加特殊权限；\n\n3. 如果条件允许，请在使用本仓库题目时同时提供数据、标程、题解等资源的获取方法；否则，请附上本仓库的 github 地址。"}],"translated_statement":null,"sample_group":[["5 6 4\n1 1 3 3\n15 9 7 1\n4 2 8 6\n3\n3\n1\n2\n2\n4\n","91\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}