题目描述
有 n 个学生构成了一棵有根树,每个学生有一个 gpa。
定义一个学生所在的专业为仅保留两端学生 gpa 相同的边时,这个学生所在的连通分量。
定义一个专业的怨气值是 max(dep[a]−dep[b]+1) s.t. a,b是专业中的学生,dep根=0,depw=depw的父亲+1。
操作 1 :给出 x 和 y,把学生 x 的 gpa 改成 y。
操作 2 :给出 x 和 y,把学生 x 所在的专业中所有点 gpa 改为 y。
操作 3 :给出 x,问学生 x 的 gpa,x 所在专业的人数,x所在专业的怨气值。
输入格式
第一行一个数 n。
第二行 n 个数表示每个节点的父亲,其中第 i 个数 $
第三行 n 个数表示每个学生的 gpa。
第四行一个数 m。
之后 m 行,每行一个两或三个数表示一次操作,类型如上述。
输出格式
对于每个 3 操作,输出一行三个数,中间用空格隔开,依次表示:学生 x 的 gpa,x 所在专业的人数,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,m≤1000。
对于另外 40% 的数据,n,m≤105,c=2,gpa 的范围在 [1,2] 中。
对于 100% 的数据,n,m≤105,c=30,gpa 的范围在 [1,30] 中。
我都懒得喷 THU 了。