QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 125 MB Total points: 100
[+5]
统计

题目描述

n 个学生构成了一棵有根树,每个学生有一个 gpa

定义一个学生所在的专业为仅保留两端学生 gpa 相同的边时,这个学生所在的连通分量。

定义一个专业的怨气值max(dep[a]dep[b]+1) s.t. a,b是专业中的学生,dep=0depw=depw+1

操作 1 :给出 xy,把学生 xgpa 改成 y

操作 2 :给出 xy,把学生 x 所在的专业中所有点 gpa 改为 y

操作 3 :给出 x,问学生 xgpax 所在专业的人数,x所在专业的怨气值。

输入格式

第一行一个数 n

第二行 n 个数表示每个节点的父亲,其中第 i 个数 $

第三行 n 个数表示每个学生的 gpa

第四行一个数 m

之后 m 行,每行一个两或三个数表示一次操作,类型如上述。

输出格式

对于每个 3 操作,输出一行三个数,中间用空格隔开,依次表示:学生 xgpax 所在专业的人数,x 所在专业的怨气值。

样例 #1

样例输入 #1

10
0 1 1 1 3 4 2 4 2 3
16 20 29 16 23 6 29 21 1 22
10
3 4
3 4
2 6 20
2 1 8
2 2 8
1 9 21
3 6
3 2
1 3 11
1 4 17

样例输出 #1

16 2 2
16 2 2
20 1 1
8 3 2

提示

Idea:ccz181078,Solution:ccz181078,Code:ccz181078,Data:ccz181078

定义 gpa 共有 c 种。

对于 40% 的数据,n,m1000

对于另外 40% 的数据,n,m105c=2gpa 的范围在 [1,2] 中。

对于 100% 的数据,n,m105c=30gpa 的范围在 [1,30] 中。

我都懒得喷 THU 了。