Skip to content

14159: 【原4159】树上路径

题目

题目描述

author: Sakiko 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4159

Description

​ 古时候帝国有\(n\)个城堡,编号从\(1\)到\(n\)。除了皇帝拥有的城堡之外,其他每个城堡都从属于某个城堡。如果两个城堡有直接从属关系,则一条双向路径连接两个城堡 ,保证整个帝国的所有城堡互相可达。

每一年,野蛮人有可能对某个城堡\(a\)发起攻击,所到之处寸草不生。此外,野蛮人不会对同一个城堡发起多次攻击。

如果某一年野蛮人没有攻击 ,则骑士就会出来巡逻,路线是从城堡\(a\)到城堡\(b\)且不会多次经过同一个城堡。在巡逻时,骑士需要休息但是他不会选择最近\(y\)年被攻击的城堡休息。具体地说,\(a\)到城堡\(b\)(不含\(a\)和\(b\))的路线中,第\(k\)个在\(y+1\)年后没被攻击的城堡会被骑士选做休息地点。你的任务就是计算每次骑士巡逻休息地点。

Input Format

​第一行一个整数\(n\),表示城堡数。

第二行\(n\)个整数,第\(i\)个数\(a[i]\)表示城堡\(i\)从属于城堡\(a[i]\),若为\(0\),表示第\(i\)个城堡是皇帝的城堡。

第三行一个整数\(m\),表示总年数。

​以下\(m\)行,其中第\(i\)行表示第\(i\)年的事件,用第一个数表示事件类型;

1 \(c[i]\): 第i年野蛮人攻击城堡\(c[i]\); 2 \(a[i] b[i] k[i] y[i]\): 含义同题面,满足\(1<=a[i],b[i],k[i]<=n;0<=y[i]<i\)。

Output Format

​ 每一次骑士巡逻的休息地点的城堡编号单独输出一行,若不需休息,则输出-1。

Sample Input

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

Sample Output

2
-1
-1
2

Data Range

对于30%的数据,\(n \le 10\)

对于另外30%的数据,不存在野蛮人进攻事件。

对于100%的数据,\(n \le 100000\)

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!