喵喵的 Query On Tree

Time Limit: 10000/5000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

喵喵每天看xiaodao做Query On Tree做的不亦乐乎!有意思嘛?QTree不是随便秒?但是她做到第一个题就卡住了,你帮喵喵搞搞嘛~~

給一棵“随机树”,这棵树是以 1 为根的树,它有 n 个节点,每个点有权值 wi,有两个操作——

1、给树上两个点u,v ,将路径 u -> v 上的所有的权值改为 x;

2、询问以第 i 个节点为根的子树中权值第 x 大的权值是多少;

比如 {1 , 2 , 3 , 4 , 4 , 5} 第 1 大的是 5 , 第2、3大的都是4,第4大的是3,等等。

注意:树的形状是随机的(除了根节点1 以外,每个点的父亲是随机的),询问的 i 也是随机的

Input

第一行一个整数 T 代表数据组数。

对于每组数据,第一行一个整数 n , 代表有 n 个节点。(1≤n≤104

第二行 n 个整数 wi 代表每个节点的初始权值。(0≤wi≤105)

第三行 n - 1 个整数 Ai ( 从 A2 开始,依次是 A3,A4,A5,A6....)代表第 i 个节点的父亲

第4行一个整数 Q 代表操作数(1≤Q≤105

以下Q行每行代表一个操作

操作1:C u v x 代表将 u->v 路径上的所有点权值改为x. (0 ≤ x ≤ 105 , 1 ≤ u , v ≤ n)

操作2:  Q i x 代表求以i为根的子树中第x大的权值是几 (1 ≤ i ≤ n 且 x 一定合法)

Output

对于每组询问输出一个整数。

Sample Input

2
5
5 0 4 0 8
4 2 1 2
5
C 1 5 2
C 3 2 6
C 4 2 3
Q 2 2
C 3 1 13
5
0 14 3 7 16
4 2 1 4
5
Q 4 2
C 1 4 10
C 3 5 11
Q 5 1
Q 3 1

Sample Output

3
14
11
11

Source

Dshawn

Manager

Information
Solved Number19
Submit Number119
Problem Tags
dfs and similar
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel