QOJ.ac

QOJ

Time Limit: 5 s Memory Limit: 2048 MB
[0]

# 7966. 采矿

Statistics

题目背景

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

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

题目描述

你是一个矿坑老板。

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

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

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

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

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

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

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

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

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

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

输入格式

从标准输入读入数据。

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

第二行 n1 个整数,其中第 i1i<n,下同)个表示 fi+1

第三行 n1 个整数,其中第 i 个表示 ri+1

第四行 n1 个整数,其中第 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

子任务

保证 2n3011q6001sn

保证 1fi<i0ri,pi109

保证相同的 fi 最多出现两次。