因为孙✌抱怨给小朋友准备的题目过于简单，突发奇想想到了这个题。

U631144 树高 - 洛谷

考虑使用 ETT 来维护子树移动。即直接维护树的欧拉环游序。

那么一次移动相当于是一个区间被移动到了另一个位置。

这个可以用平衡树来维护，同时需要区间加区间 $\max$。

如果精细实现的话复杂度 $O(n+q\log n)$。但是比较懒没有卡 $O((n+q)\log n)$。

同时可以发现其实即使 $v$ 在 $u$ 的子树内也是可以交换的，只不过较为繁琐。

本来想卡块状链表但平衡树常数太大，不一定卡的掉。

由于深度的差分数组只存在 $1,-1$，因此对于 $10^5$ 的做法也许可以用 bitset 维护。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<bits/stdc++.h>
#define rep(a,b,c) for(int c(a);c<=(b);++c)
#define drep(a,b,c) for(int c(a);c>=(b);--c)
using namespace std;
inline int read()
{
	int res=0;char ch=getchar();while(ch<'0'||ch>'9')ch=getchar();
	while(ch<='9'&&ch>='0')res=res*10+(ch^48),ch=getchar();return res;
}
const int N=1e6+10;unsigned seed=998244353;
inline unsigned rnd(){seed^=seed<<17;seed^=seed>>13;seed^=seed<<5;return seed;}
struct Node
{
	int l,r,f,siz,mxd,tag,val;unsigned key;
	inline void operator += (int x){val+=x;tag+=x;mxd+=x;}
	inline Node(int x=0){l=r=f=tag=0;siz=1;key=rnd();mxd=val=x;}
}t[N<<1];
int Rt,T1,T2,T3,T4,n,q,cnt,cdt;vector<int> T[N];
int ql[N],qr[N],dfn[N<<1],dep[N],stk[N<<1],top;
inline void update(int k)
{
	t[k].siz=1;t[k].mxd=t[k].val;t[k].f=0;
	if(t[k].l)t[k].siz+=t[t[k].l].siz,t[k].mxd=max(t[t[k].l].mxd,t[k].mxd),t[t[k].l].f=k;
	if(t[k].r)t[k].siz+=t[t[k].r].siz,t[k].mxd=max(t[t[k].r].mxd,t[k].mxd),t[t[k].r].f=k;
}
inline void pushdown(int k)
{
	if(!t[k].tag)return;int &x=t[k].tag;
	if(t[k].l)t[t[k].l]+=x;if(t[k].r)t[t[k].r]+=x;x=0;
}
inline void split(int k,int cur,int &x,int &y)
{
	if(!cur){x=y=0;return;}pushdown(cur);
	if(k<=t[t[cur].l].siz){split(k,t[cur].l,x,t[y=cur].l);update(cur);return;}
	else {split(k-t[t[cur].l].siz-1,t[cur].r,t[x=cur].r,y);update(cur);return;}
}
inline int merge(int L,int R)
{
	if(!L||!R)return L+R;pushdown(L);pushdown(R);
	if(t[L].key<t[R].key){t[L].r=merge(t[L].r,R);update(L);return L;}
	else{t[R].l=merge(L,t[R].l);update(R);return R;}
}
inline int rnk(int k)
{
	int res=t[t[k].l].siz;
	while(t[k].f)
	{
		stk[++top]=t[k].f;
		res+=(k==t[t[k].f].r)?t[t[t[k].f].l].siz+1:0;k=t[k].f;
	}
	while(top)pushdown(stk[top--]);
	return res+1;
}
inline void dfs(int u=1)
{
	ql[u]=++cdt;dfn[cdt]=u;
	for(int v:T[u]){dep[v]=dep[u]+1;dfs(v);}
	qr[u]=++cdt;dfn[cdt]=u;
}
inline int newNode(int x){t[++cnt]=Node(x);return cnt;}
int main()
{
	ios::sync_with_stdio(false);
	n=read();q=read();rep(2,n,i)T[read()].push_back(i);
	dfs();rep(1,n*2,i)Rt=merge(Rt,newNode(dep[dfn[i]]));
	t[0].siz=0;while(q--)
	{
		int u=read(),v=read();
		int ul=rnk(ql[u]),ur=rnk(qr[u]),vl=rnk(ql[v]),vr=rnk(qr[v]);
		int du=t[ql[u]].val,dv=t[ql[v]].val;
		if(!(dv>=du&&ul<=vl&&vr<=ur))
		{
			split(ur,Rt,T1,T3);
			split(ul-1,T1,T1,T2);
			Rt=merge(T1,T3);
			t[T2]+=(dv-du+1);
			split(rnk(qr[v])-1,Rt,T1,T3);
			Rt=merge(merge(T1,T2),T3);
		}
		rnk(ql[u]);
		printf("%d %d\n",t[ql[u]].val,t[Rt].mxd);
	}
}