#P3460. Jc的宿舍

Jc的宿舍

Jc 的宿舍

题目描述

宿舍构成一棵有 nn 个节点的树,每个节点住着一个人。11 号宿舍住着 Jc,水龙头起初也位于 11 号宿舍。第 ii 个人装满水桶需要 TiT_i 单位时间。

水龙头的位置可能改变。住在某个宿舍的人出发打水时,会沿树上到水龙头的唯一路径走,路径上所有宿舍的人都参加这次打水,包括出发宿舍和水龙头所在的宿舍。

每次打水时,这些人可以任意安排接水顺序,水龙头同一时间只能为一个人接水。一个人的等待时间从开始接水前计起,到自己的水桶灌满为止,包含前面的人和自己接水所用的时间。求所有参与者的等待时间总和的最小值。

输入格式

第一行包含三个整数 n,m,keyn,m,\mathrm{key},表示宿舍数、事件数和用于解码查询的参数。

第二行包含 nn 个整数 T1,…,TnT_1,\dots,T_n,每个 Ti≤107T_i\le 10^7。

第三行包含 nn 个整数,第 ii 个整数是 ii 号宿舍的父节点编号。11 号宿舍的父节点为 00。

接下来 mm 行,每行是以下两种事件之一。

  • C i 表示把水龙头移动到 ii 号宿舍。
  • Q k 表示一次打水查询。实际出发宿舍的编号为$$\bigl(k+(\mathrm{pre}\bmod 2)\times \mathrm{key}\bigr)\bmod n+1,$$其中 pre\mathrm{pre} 为上一次查询的答案。第一次查询时 pre=0\mathrm{pre}=0。

输出格式

对每个 Q 事件输出一行一个整数,表示此次打水的最小总等待时间。

样例 #1

3 2 0
2 2 1
0 3 1
C 3
Q 1
4