Mon2tr

Problem Description

请注意本题特殊的空间限制。 “生命野蛮蓬勃，大地千变万化。人造机器轰鸣运作，源石能的光辉照亮了暗影。人们挣扎在暗处，向往光明，在辉煌时轻视阴影，如是反复。” 给定一棵由编号为 $1,2,3,\cdots,n$ 的点构成的有根树。记 $d_i$ 表示编号为 $i$（$1\le i\le n$）的点到树根的唯一简单路径上的 点数 （对于树根本身，这个值为 $1$）。 现在有 $q$ 次询问。第 $i$（$1\le i\le q$）次询问给定整数 $x_i,y_i,z_i$。对于整数 $j$（$1\le j\le n$），定义 $v_j=d_{\text{LCA}(j,x_i)}$，其中 $\text{LCA}(u,v)$ 表示编号分别为 $u,v$ 的点的最近公共祖先的编号。 对于第 $i$（$1\le i\le q$）次询问，求满足 $j-v_j\le y_i\le j\le j+v_j\le z_i$ 的整数 $j$（$1\le j\le n$）中，$j+v_j$ 的最大值。如果 $y_i>z_i$ 或者不存在符合条件的整数，答案为 $0$。

Input

本题包含多组测试数据。 来自 Kal'tsit 的温馨提示：本题输入输出量较大，请使用合适的输入输出方式。你可以使用下面链接中给出的输入输出模板。同时请选手注意代码的时间和空间常数消耗，常数过大，例如滥用 C++ STL 容器的代码不保证能够通过。

https://www.luogu.me/paste/y4lm88ha

char buf[1<<22],*p1,*p2;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<22,stdin),p1==p2)?EOF:*p1++)
inline int read(){
	int x=0;char ch=0;
	while((ch<'0'||ch>'9'))ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch-'0'),ch=getchar();
	return x;
}
inline void write(int x,char tl=0){
	static int sta[10];
	int top=0;
	do{sta[top++]=x%10,x/=10;}while(x);
	while(top)putchar(sta[--top]+48);
	if(tl)putchar(tl);
}

首先在第一行输入一个整数 $T$（$1\le T\le3.5\times10^5$）表示测试数据组数。 对于每一组测试数据，输入包含 $q+2$ 行。 第一行包含两个整数 $n,q$（$1\le n\le 8\times10^4,1\le q\le 10^5$，$1\le\sum n\le3.5\times10^5,1\le \sum q\le 5\times 10^5$），分别表示树上点的数量和询问的次数。 第二行包含 $n$ 个整数 $fa_1,fa_2,fa_3,\cdots,fa_n$（$0\le fa_1,fa_2,fa_3,\cdots,fa_n\le n$）表示每个点的父亲编号。若 $fa_i=0$（$1\le i\le n$）则表示编号为 $i$ 的点为树根。 接下来 $q$ 行，第 $i+2$（$1\le i\le q$）行包含三个整数 $x'_i,y'_i,z'_i$（$0\le x'_i,y'_i,z'_i<10^9$），表示与第 $i$ 次询问的参数有关的三个数。 对于第 $i$（$1\le i\le q$）次询问，你需要通过以下操作得到 $x_i,y_i,z_i$：

1. 记 $lans$ 表示第 $i-1$ 次询问的答案。若 $i=1$，则令 $lans=0$。
2. $x_i=[(x'_i+lans)\bmod n]+1$，$y_i=[(y'_i+lans)\bmod(2n-1)]-(n-1)$，$z_i=[(z'_i+lans)\bmod(2n-1)]+1$，其中 $\bmod$ 表示取模，例如 $3\bmod 2=1,(-7)\bmod 3=2$。 保证输入的是一棵有根树。

Output

对于每一组测试数据，输出包含 $q$ 行。 第 $i$（$1\le i\le q$）行包含一个整数表示第 $i$ 次询问的答案。

Sample Input

5
5 5
2 3 4 5 0
3 428538 54277
3 417360 4017
3 892741 445551
4 964351 433610
4 472928 556419
5 5
2 0 5 3 1
2 145658 137247
5 616008 743457
3 236233 341788
5 338103 325826
2 722091 315410
5 5
5 0 4 2 3
1 904355 654626
2 418807 822821
4 45452 454729
5 4372 624796
3 138698 133893
5 5
2 0 1 5 2
1 698219 122911
5 682494 893039
3 293682 893575
1 804585 301494
5 634397 319946
15 15
5 4 4 9 3 7 9 15 0 3 12 6 9 3 9
2 305062 35660
3 843437 749658
11 170333 369270
1 311572 416623
8 860851 743360
4 16581 926304
5 369493 824555
6 517688 889937
8 710314 148564
7 21922 973381
13 790964 3688
7 989786 105365
1 359041 27784
6 623431 2814
6 678899 377943

Sample Output

3
6
0
0
3
0
3
2
0
3
0
0
5
0
0
6
0
0
0
5
0
0
4
0
3
13
7
8
0
17
0
4
0
0
0

Hint

在样例的第一组测试数据中，树的结构如下图所示。 这组测试数据共有 $5$ 次询问。 在第 $1$ 次询问中，$x_1=4,y_1=-1,z_1=8$。

1. 若 $j=1$，则 $j-v_j=-1,j+v_j=3$，满足 $j-v_j\le y_1\le j\le j+v_j\le z_1$。
2. 若 $j=2$，则 $j-v_j=0,j+v_j=4$，不满足题意。
3. 若 $j=3$，则 $j-v_j=1,j+v_j=5$，不满足题意。
4. 若 $j=4$，则 $j-v_j=2,j+v_j=6$，不满足题意。
5. 若 $j=5$，则 $j-v_j=4,j+v_j=6$，不满足题意。 因此，答案为 $3$。
6. 在第 $2$ 次询问中，$x_2=2,y_2=2,z_2=7$。取 $j=2/3/4$，答案为 $6$。
7. 在第 $3$ 次询问中，$x_3=5,y_3=-3,z_3=4$。答案为 $0$。
8. 在第 $4$ 次询问中，$x_4=5,y_4=-3,z_4=9$。答案为 $0$。
9. 在第 $5$ 次询问中，$x_5=5,y_5=1,z_5=4$。取 $j=2$，答案为 $3$。 在样例的第五组测试数据中，树的结构如下图所示。 这组测试数据共有 $15$ 次询问。
10. 在第 $1$ 次询问中，$x_1=3,y_1=-3,z_1=20$。答案为 $0$。
11. 在第 $2$ 次询问中，$x_2=4,y_2=-13,z_2=9$。答案为 $0$。
12. 在第 $3$ 次询问中，$x_3=12,y_3=2,z_3=14$。取 $j=3$，答案为 $4$。
13. 在第 $4$ 次询问中，$x_4=6,y_4=-14,z_4=14$。答案为 $0$。
14. 在第 $5$ 次询问中，$x_5=9,y_5=1,z_5=4$。取 $j=2$，答案为 $3$。
15. 在第 $6$ 次询问中，$x_6=8,y_6=11,z_6=19$。取 $j=12$，答案为 $13$。
16. 在第 $7$ 次询问中，$x_7=4,y_7=3,z_7=12$。取 $j=5$，答案为 $7$。
17. 在第 $8$ 次询问中，$x_8=14,y_8=2,z_8=22$。取 $j=5$，答案为 $8$。
18. 在第 $9$ 次询问中，$x_9=2,y_9=11,z_9=6$。答案为 $0$。
19. 在第 $10$ 次询问中，$x_{10}=8,y_{10}=13,z_{10}=26$。取 $j=15$，答案为 $17$。
20. 在第 $11$ 次询问中，$x_{11}=1,y_{11}=-8,z_{11}=23$。答案为 $0$。
21. 在第 $12$ 次询问中，$x_{12}=8,y_{12}=2,z_{12}=9$。取 $j=3$，答案为 $4$。
22. 在第 $13$ 次询问中，$x_{13}=6,y_{13}=11,z_{13}=7$。答案为 $0$。
23. 在第 $14$ 次询问中，$x_{14}=7,y_{14}=4,z_{14}=2$。答案为 $0$。
24. 在第 $15$ 次询问中，$x_{15}=7,y_{15}=-5,z_{15}=16$。答案为 $0$。

Source

2025“钉耙编程”中国大学生算法设计暑期联赛（4）