UOJ Logo

NOI.AC

#77. 路径

统计

路径(path)

问题描述

给定一棵树,动态地维护以下操作:

  • u 标记一个点(标记不可逆)

  • u v k y 不考虑y+1时刻之前的操作,询问u到v的路径上第k个未被标记的点(u,v不被计入)

输入格式

第一行1个整数$n (1\leq n\leq 10^5)$,表示点数。

第二行n个整数,第i个数表示点i的父结点标号,如果是0表示当前是根结点。

第三行1个整数$m(1\leq m\leq10^5)$,表示操作数。

接来来m行,每行一个操作1 ui或者2 ui vi ki yi(1<=ui,vi<=n,yi< i)。

输出格式

对于每个询问输出一行答案,表示路径上第k个未被标记的点,如果没有则输出-1。

输入样例1

10
8 9 8 1 8 1 1 0 10 4
3
1 8
2 2 1 1 1
1 6

输出样例1

9

输入样例2

6
5 5 1 5 0 5
3
2 6 2 1 0
2 1 5 2 1
1 2

输出样例2

5
-1

数据范围和约定

对于10%的数据$n\leq100,m\leq100$。

对于30%的数据 $n\leq1000,m\leq1000$

另有30%的数据 保证$y$全为0

对于100%的数据$n\leq10^5,m\leq10^5$。