Noble Knight's Path

题意翻译

## 题目描述 在Berland，每个领主都拥有一个城堡，每个城堡都属于一个领主。 在这个领主制度中，除了国王一个人，都隶属于另一个领主。每个领主都可以有任意数量的附庸（下属）。 有些城堡是通过双向道路连接起来的。两个城堡之间有一条路当且仅当其中一个城堡的领主是另一个城堡领主的直接下属。 每年，Berland可能发生以下两件事中的一件： 1. 野蛮人袭击了城堡c。有趣的是，在整个Berland的历史中，野蛮人从未两次袭击同一座城堡。也就是说，这是这座城堡第一次也是最后一次受到攻击。 2. 一个高贵的骑士踏上了从城堡A到城堡B的旅程（他从不重复经过任何一座城堡，因此他的路是唯一确定的）。 让我们考虑事件二。从城堡A到城堡B的旅程漫长无比，那么骑士可能会想要在他在路上遇到的城堡停下来休息。然而，他不能在这样的城堡停留：因为他是**高贵的骑士**，所以他不能呆在被野蛮人的~~恶臭~~亵渎的城堡里。一座城堡一旦在第y年受到攻击，就会被亵渎。所以，骑士选择他在从a到b路途中（当然不包含a和b）遇到的第k座没有被亵渎的城堡来休息。总而言之，骑士会选择途经的第k个**从第y+1年开始到现在**没有被亵渎的城堡（不算城堡a和b）。 然而，问题总是这样，骑士们不记得哪些城堡在什么时候被亵渎了。所以，他只好请来鼎鼎有名的~~OIer~~历史学家，也就是你，来帮助他们。 你可以知道Berland历史上有一连串的事件。告诉每一个骑士，在哪个城市他应该停下来，或者告诉他一个不幸的消息——从城堡a到城堡b的道路上，只有不到k个城市符合他的要求，所以他不能休息。 **P.S.译者提示：对于选择第y年旅行的某个骑士，只有在第y+1年开始到现在被亵渎的城堡才不能休息。我们并不考虑在第1年到第y年被亵渎的城堡，也就是说，这些城堡是可以休息的。** ## 输入输出格式 #### 输入格式： 第一行包含一个整数n($2 \leq n \leq 10^5$)，表示领主的个数。 第二行包含包含n个整数，第i个整数表示编号为i的领主上级的编号。自然，领主i的城堡编号也是i。**特别的，国王没有上级，故用0代替。** 第三行包含一个整数m($2 \leq m \leq 10^5$)，表示Berland的历史年数。 接下来的m行，第i行描述了这一年发生的事件。 对于第i行，首先给出一个整数$t_i(1 \leq t_i \leq 2)$。 对于$t_i=1$，再给出一个整数$c_i(1 \leq c_i \leq n)$，表示这一年野蛮人攻击了城堡$c_i$。 对于$t_i=2$，再给出四个整数$a_i,b_i,k_i,y_i(1 \leq a_i,b_i,k_i \leq n$，$0 \leq y_i \leq i)$，表示某个骑士决定在第$y_i$年，从城堡$a_i$出发，到城堡$b_i$，在第$k_i$个没有被亵渎的城堡休息。 #### 输出格式： 对于每个$t_i=2$，每行给出一个整数，表示这个骑士可以休息的城堡。如果不存在休息地，输出-1。 ## 说明 #### 样例解释： 在样例1中，只有城堡2在骑士从城堡1到城堡3的路上。当第一年骑士第一次的旅程经过路径1−3，城堡2没有被亵渎所以骑士可以在那里休息。第二年，城堡2被攻击了，所以骑士并不会在那里休息，因此接下来的两次旅程中，他没有地方休息了（当发现了一个没有被亵渎的城堡，对他来说是很重要的）。在第五年骑士第四次的旅程中，他并不会在意城堡2被亵渎过（因为他选择了第二年旅行，而城堡2恰好在第二年被亵渎。根据规则，这并不在这个骑士的介意范围内），所以他可以在城堡2休息。 #### 数据规模与约定： 对于所有的数据，$2 \leq n,m \leq 10^5$，$1 \leq a_i,b_i,k_i \leq n$，$0 \leq y_i \leq i$。数据保证对于每个$a_i$和$b_i$，都有$a_i \neq b_i$，并且国王有且仅有一个。 感谢@lzzVIL 提供的翻译

题目描述

In Berland each feudal owns exactly one castle and each castle belongs to exactly one feudal. Each feudal, except one (the King) is subordinate to another feudal. A feudal can have any number of vassals (subordinates). Some castles are connected by roads, it is allowed to move along the roads in both ways. Two castles have a road between them if and only if the owner of one of these castles is a direct subordinate to the other owner. Each year exactly one of these two events may happen in Berland. 1. The barbarians attacked castle $ c $ . The interesting fact is, the barbarians never attacked the same castle twice throughout the whole Berlandian history. 2. A noble knight sets off on a journey from castle $ a $ to castle $ b $ (provided that on his path he encounters each castle not more than once). Let's consider the second event in detail. As the journey from $ a $ to $ b $ is not short, then the knight might want to stop at a castle he encounters on his way to have some rest. However, he can't stop at just any castle: his nobility doesn't let him stay in the castle that has been desecrated by the enemy's stench. A castle is desecrated if and only if it has been attacked after the year of $ y $ . So, the knight chooses the $ k $ -th castle he encounters, starting from $ a $ (castles $ a $ and $ b $ aren't taken into consideration), that hasn't been attacked in years from $ y+1 $ till current year. The knights don't remember which castles were attacked on what years, so he asked the court scholar, aka you to help them. You've got a sequence of events in the Berland history. Tell each knight, in what city he should stop or else deliver the sad news — that the path from city $ a $ to city $ b $ has less than $ k $ cities that meet his requirements, so the knight won't be able to rest.

输入输出格式

输入格式

The first input line contains integer $ n $ $ (2<=n<=10^{5}) $ — the number of feudals. The next line contains $ n $ space-separated integers: the $ i $ -th integer shows either the number of the $ i $ -th feudal's master, or a $ 0 $ , if the $ i $ -th feudal is the King. The third line contains integer $ m $ $ (1<=m<=10^{5}) $ — the number of queries. Then follow $ m $ lines that describe the events. The $ i $ -th line (the lines are indexed starting from $ 1 $ ) contains the description of the event that occurred in year $ i $ . Each event is characterised by type $ t_{i} $ $ (1<=t_{i}<=2) $ . The description of the first type event looks as two space-separated integers $ t_{i} $ $ c_{i} $ $ (t_{i}=1; 1<=c_{i}<=n) $ , where $ c_{i} $ is the number of the castle that was attacked by the barbarians in the $ i $ -th year. The description of the second type contains five space-separated integers: $ t_{i} $ $ a_{i} $ $ b_{i} $ $ k_{i} $ $ y_{i} $ $ (t_{i}=2; 1<=a_{i},b_{i},k_{i}<=n; a_{i}≠b_{i}; 0<=y_{i}&lt;i $ ), where $ a_{i} $ is the number of the castle from which the knight is setting off, $ b_{i} $ is the number of the castle to which the knight is going, $ k_{i} $ and $ y_{i} $ are the $ k $ and $ y $ from the second event's description. You can consider the feudals indexed from 1 to $ n $ . It is guaranteed that there is only one king among the feudals. It is guaranteed that for the first type events all values $ c_{i} $ are different.

输出格式

For each second type event print an integer — the number of the castle where the knight must stay to rest, or -1, if he will have to cover the distance from $ a_{i} $ to $ b_{i} $ without a rest. Separate the answers by whitespaces. Print the answers in the order, in which the second type events are given in the input.

输入输出样例

输入样例 #1

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

输出样例 #1

2
-1
-1
2

输入样例 #2

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

输出样例 #2

5
-1

说明

In the first sample there is only castle $ 2 $ on the knight's way from castle $ 1 $ to castle $ 3 $ . When the knight covers the path $ 1-3 $ for the first time, castle $ 2 $ won't be desecrated by an enemy and the knight will stay there. In the second year the castle $ 2 $ will become desecrated, so the knight won't have anywhere to stay for the next two years (as finding a castle that hasn't been desecrated from years $ 1 $ and $ 2 $ , correspondingly, is important for him). In the fifth year the knight won't consider the castle $ 2 $ desecrated, so he will stay there again.