A8731. Noble Knight's Path
编程题
普及/提高-
知识点
题目描述
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.
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}<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.
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}<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.
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.