#P3460. Jc的宿舍
Jc的宿舍
Jc 的宿舍
题目描述
宿舍构成一棵有 个节点的树,每个节点住着一个人。 号宿舍住着 Jc,水龙头起初也位于 号宿舍。第 个人装满水桶需要 单位时间。
水龙头的位置可能改变。住在某个宿舍的人出发打水时,会沿树上到水龙头的唯一路径走,路径上所有宿舍的人都参加这次打水,包括出发宿舍和水龙头所在的宿舍。
每次打水时,这些人可以任意安排接水顺序,水龙头同一时间只能为一个人接水。一个人的等待时间从开始接水前计起,到自己的水桶灌满为止,包含前面的人和自己接水所用的时间。求所有参与者的等待时间总和的最小值。
输入格式
第一行包含三个整数 ,表示宿舍数、事件数和用于解码查询的参数。
第二行包含 个整数 ,每个 。
第三行包含 个整数,第 个整数是 号宿舍的父节点编号。 号宿舍的父节点为 。
接下来 行,每行是以下两种事件之一。
C i表示把水龙头移动到 号宿舍。Q k表示一次打水查询。实际出发宿舍的编号为$$\bigl(k+(\mathrm{pre}\bmod 2)\times \mathrm{key}\bigr)\bmod n+1,$$其中 为上一次查询的答案。第一次查询时 。
输出格式
对每个 Q 事件输出一行一个整数,表示此次打水的最小总等待时间。
样例 #1
3 2 0
2 2 1
0 3 1
C 3
Q 1
4