题目背景
_“我已经买不起第二个机器人了。”_
_“那就雇点人来凑数吧。注意别给死里头。”_
题目描述
你是一个矿坑老板。
你的矿坑是二叉树形结构,有 n 个节点。1 号点为地面,对于所有的 2≤i≤n,i 号节点与更浅层的 fi 号节点通过通道相连,其中 fi<i,且相同的 fi 最多出现两次。矿坑的不同节点的产量和开采难度均不相同。对于 i 号节点 (2≤i≤n),如果派一个机器人开采,一单位时间内能有 ri 的产出;如果派一个人类开采,一单位时间内能有 pi 的产出。地面没有产出。
你有一个机器人,初始位于 s 号节点。你的矿坑里初始没有人类工人。
所有通道与节点都十分狭窄,每个节点都只能容下一名工人(工人包括人类和机器人),每个通道也只能恰好容一名工人通过。在移动的任何时刻,只能有最多一名工人在通道中,其余工人都必须在节点上。
你现在有 q 条计划需要按顺序执行。每个计划分为准备、执行、调整、开采四个阶段。
在准备阶段,人类可以在满足上述移动规则的前提下任意移动,但不能进入或离开矿坑(矿坑内的工人到达 1 号节点不算离开矿坑),因为你在看着他们;移动的顺序和次数均没有限制。机器人不能移动。
在执行阶段,不同计划需要做的事情可能不同,共分为 4 种:
- 机器人只能沿通道向更浅的方向移动,且至少需要经过一条通道。人类不能移动。
- 机器人只能沿通道向更深的方向移动,且至少需要经过一条通道。人类不能移动。
- 使一名人类从 1 号节点进入矿坑(这意味着该阶段开始时 1 号节点上必须没有工人)。除此之外所有工人都不能移动。
- 使一名人类从 1 号节点移出矿坑(这意味着该阶段开始时 1 号节点上必须有一名人类)。除此之外所有工人都不能移动。
在调整阶段,限制与准备阶段相同。人类可以在满足上述移动规则的前提下任意移动,但不能进入或离开矿坑;移动的顺序和次数均没有限制。机器人不能移动。
在开采阶段,所有的工人会采一单位时间的矿。所有有工人的非地面节点会根据位于该节点的工人种类计算产出。没有工人的节点没有产出。该计划的产出为所有节点的产出之和。
问按顺序执行完所有计划之后,你所有计划的产出之和最多可以达到多少。
输入格式
从标准输入读入数据。
第一行三个正整数 n,q,s。
第二行 n−1 个整数,其中第 i(1≤i<n,下同)个表示 fi+1。
第三行 n−1 个整数,其中第 i 个表示 ri+1。
第四行 n−1 个整数,其中第 i 个表示 pi+1。
接下来 q 行,每行一个整数表示计划的种类,其中第 i 个整数表示第 i 条计划:
1
表示第一种计划:将机器人向更浅的方向移动;2
表示第二种计划:将机器人向更深的方向移动;3
表示第三种计划:将一名人类从 1 号节点送入矿坑;4
表示第四种计划:将一名人类从 1 号节点移出矿坑。
输出格式
输出到标准输出。
如果无论如何你都无法完成你的计划,输出一行 No solution.
。否则输出一行一个整数,表示你的产出之和的最大值。
样例1输入
5 6 4
1 1 3 3
15 9 7 1
4 2 8 6
3
3
1
2
2
4
样例1输出
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≤n≤301,1≤q≤600,1≤s≤n。
保证 1≤fi<i,0≤ri,pi≤109。
保证相同的 fi 最多出现两次。