by chenzhe

我们可以用一棵表示管理关系的树来刻画问题，其中每个结点的权值为该长官的成员数。注意，如果存在两名高级长官（影响力不小于 $M/2$），那么其中一人一定是另一人的祖先。

我们要寻找树中深度最大的结点，使其子树大小至少为整棵树的一半；这里计算子树大小时，需要计入每个结点的权值。这本质上是在寻找带权树的重心；若存在多个候选结点，则选择离根最远的一个。我们可以从根开始，只要还能继续，就向子树最大的儿子移动。

不过，这棵树还会发生变化：可以把以 $x$ 为根、原本连接在结点 $y$ 下方的一棵子树断开，再把它接到别处，作为结点 $z$ 的儿子。

子任务 1

为了向重心方向不断下降，需要维护每个结点的儿子列表。移动一棵子树时，可以用 $O(n)$ 的时间更新受影响的两份儿子列表。随后下降过程需要 $O(n)$ 步，每一步再用 $O(n)$ 的时间计算子树大小。因此，每次修改后可以在 $O(n^2)$ 的时间内重新求出答案。

子任务 2

上一种解法的瓶颈是计算子树大小。我们可以只更新断开位置和重新连接位置处所有祖先的子树大小。这样便能在 $O(n)$ 的时间内求出答案。

子任务 3

为了进一步优化，我们需要在支持子树移动的同时，更快地在树上移动。可以使用根号分治：从叶子向根处理整棵树，不断把结点组成块（每个块都是一棵子树），直到一个块的大小超过 $\sqrt n$。这样会得到 $O(\sqrt n)$ 个深度为 $O(\sqrt n)$ 的块。不过，单个块仍可能包含 $O(n)$ 个结点，例如根有许多较小的儿子，而这些儿子自身都没有形成独立的块。

还需要考虑移动子树时会发生什么。可以把这棵子树单独切出，让它形成一个新块，再将新块接到其他位置。若 $x$ 原本不是某个块的根，而我们必须从 $x$ 处切开，则形成的新块至多包含 $O(\sqrt n)$ 个结点。枚举这些结点，就能找出所有需要改为指向新块的子块。随着块的数量不断增加，可以每进行 $O(\sqrt n)$ 次移动，就用 $O(n)$ 的时间重构整棵树的分块结构，从而得到均摊 $O(\sqrt n)$ 的时间复杂度。

接下来说明如何在这种结构中寻找重心。若仍从根向下走，就需要更新全部 $O(n)$ 个祖先的子树大小，代价过高。可以改为分别从 $y$ 和 $z$ 向上移动，并在两条路径上寻找最近的、子树大小足够大的结点。一旦到达它们的最近公共祖先，更高处结点的子树大小便不会发生变化，因此重心也不会相对于上一次修改继续改变。

向上的过程可以先整块跳跃；移动子树时需要重新计算块的大小。到达最后一个块后，再在块内逐个结点移动。该块的高度为 $O(\sqrt n)$，而且只需更新实际访问到的结点的子树大小。于是，可以在 $O(\sqrt n)$ 的时间内求出新重心，或判断重心没有变化。

子任务 4

为了达到更高效率，需要换一种方式表示树。树的 Euler Tour 会给出一个结点序列，其中每棵子树都对应一段连续子序列。若用平衡树结构（例如 treap 或伸展树）维护这个 Euler Tour，就能高效删除和插入序列中的一段，而这恰好对应移动一棵子树。这种表示也称为 Euler Tour Tree。它让移动子树变得简单，却使查询某个结点的祖先等操作更复杂。

还需要维护一些附加信息。在 Euler Tour 中存储结点在原树中的深度 $d(x)$；在维护 Euler Tour 的 treap 中，存储每棵 treap 子树内的最小深度。移动以 $x$ 为根的子树时，$x$ 子树内所有结点的深度都会改变，改变量由连接位置 $y$ 与 $z$ 的深度差决定。可以在 treap 上打懒标记，一次性延迟更新整棵子树的深度变化。

如上一子任务所述，新重心要么位于 $y$ 与 $z$ 之间的路径上，要么根本不变。$\operatorname{lca}(y,z)$ 的祖先的子树大小不会改变，因此它们不会影响对新重心的搜索。我们分别把 $y$ 和 $z$ 向上提升，寻找其最低的、子树大小足够大的祖先。可以进行一种二进制搜索：按照从大到小的二次幂依次尝试第 $2^i$ 个祖先。

为此，需要高效求出给定结点的第 $k$ 个祖先。在 Euler Tour 中，结点 $x$ 的第 $k$ 个祖先对应序列中最靠右的、深度等于 $d(x)-k$ 的元素。在 treap 表示中，可以利用维护的最小深度，引导搜索走向深度符合要求的最靠右结点。

该解法的时间复杂度为 $O((\log n)^2)$：需要考虑 $O(\log n)$ 个祖先，而每次确定祖先都需要在 treap 中进行一次 $O(\log n)$ 的搜索。

Link-Cut Tree 是一种更高级、能够支持树或森林修改的数据结构。用类似的方法，它可以在均摊 $O(\log n)$ 的时间内解决本题，不过拿到满分并不要求使用它。

生成式人工智能辅助说明

本文由 OpenAI Codex 根据用户提供的 CEOI 2026 第一日官方英文题解翻译、排版并统一数学公式格式；算法思路、论证与复杂度均来自原文，未另行生成新的解法。

好像直接 LCT 就可以做/yun。但是不会 LCT 怎么办。

不难发现，满足和 $\ge \frac{M}{2}$ 的点呈现祖先关系。且新的答案一定会在 $x$ 或 $lastans$ 的祖先中。我们只要能求出两个点祖先中最深的满足和 $\ge \frac{M}{2}$ 的点就能求出新的答案。

首先考虑如何支持询问一个点的子树和。我们用平衡树维护类似 dfs 的入栈出栈序，是一个括号序列的形式。我们将一个节点 $x$ 的前括号的编号设为 $x$，后括号设为 $x+n$。询问时，在平衡树中找到这两个位置，不断跳父亲，可以求出前缀和，再相减即可。

维护这个序列就是每次分裂出 $x$ 的子树，将其插到 $y$ 之后即可。

如果我们能快速求出一个点的 $k$ 级祖先，我们就能直接二分了。

考虑随机撒 $O(\sqrt{n})$ 个点，将他们染成黑色。则每个点距离他祖先中最近的黑点的距离为 $\sqrt{n}$ 级别。我们要求一个点祖先中最深的满足和 $\ge \frac{M}{2}$ 的点，就可以先把其祖先中的黑点都提出来。现在标记点上二分，然后就确定答案在某一段中，再把这一段的点都提出来二分，就能求出答案。

我们需要维护每个黑点祖先中最近的黑点。这在维护出每个黑点的 dfs 序的条件下是简单的。

于是复杂度为 $O(n+q\sqrt{n}+q\log^2 n)$。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int n,q,Root,root,fa[N],mk[N],f[N],id[N],dfn[N];
int head[N],nxt[N],xl[N<<1],idx,stk[N<<1],top;
int sum[N],P;
mt19937 rnd(1145141);
struct Treap{int ls,rs,pos,val,sum,sz,fa;}t[N<<1];

// 快速读入函数
inline void read(int &x){
    x=0;int f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    x*=f;
}

// 快速输出函数
inline void print(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>9)print(x/10);
    putchar(x%10+'0');
}

inline void pc(char c){
    putchar(c);
}

inline void flush(){
    fflush(stdout);
}

void dfs(int p,int lst){
	xl[++idx]=p;
	dfn[p]=idx;
	if(mk[p]) f[p]=lst,lst=p;
	sum[p]=t[p].val;
	for(int v=head[p];v;v=nxt[v]) dfs(v,lst),sum[p]+=sum[v];
	xl[++idx]=p+n;
}
inline void pushup(int p){
	t[p].sum=t[t[p].ls].sum+t[t[p].rs].sum+t[p].val;
	t[p].sz=t[t[p].ls].sz+t[t[p].rs].sz+1;
	t[t[p].ls].fa=t[t[p].rs].fa=p,t[p].fa=0;
}
void merge(int x,int y,int &p){
	if(!x||!y) return p=x^y,void();
	if(t[x].pos<t[y].pos) merge(t[x].rs,y,t[p=x].rs);
	else merge(x,t[y].ls,t[p=y].ls);
	pushup(p);
}
void split(int p,int &x,int &y,int k){
	if(!p) return x=y=0,void();
	if(t[t[p].ls].sz>=k) split(t[p].ls,x,t[y=p].ls,k);
	else split(t[p].rs,t[x=p].rs,y,k-t[t[p].ls].sz-1);
	pushup(p);
}
inline int qrk(int p){
	int rk=1+t[t[p].ls].sz;
	for(;t[p].fa;p=t[p].fa) if(t[t[p].fa].rs==p) rk+=t[t[p].fa].sz-t[p].sz;
	return rk;
}
inline int qsum(int p){
	int res=t[t[p].ls].sum;
	for(;t[p].fa;p=t[p].fa) if(t[t[p].fa].rs==p) res+=t[t[p].fa].sum-t[p].sum;
	return res;
}
inline int find(int p){
	while(!mk[p]) p=fa[p];
	return p;
}
inline int subs(int p){return qsum(p+n)-qsum(p);}
int s[N],cnt;
inline pair<int,int> query(int p){
	cnt=0;
	if(!mk[p]) s[cnt=1]=p;
	for(int i=find(p);i;i=f[i]) s[++cnt]=i;
	int l=1,r=cnt-1,k=cnt;
	while(l<=r){
		int mid=(l+r)>>1;
		if(subs(s[mid])*2>=sum[Root]) k=mid,r=mid-1;
		else l=mid+1;
	}
	if(k==1) return make_pair(subs(p),p);
	cnt=0;
	for(int i=fa[s[k-1]];;i=fa[i]){
		s[++cnt]=i;
		if(mk[i]) break;
	}
	l=1,r=cnt-1,k=cnt;
	while(l<=r){
		int mid=(l+r)>>1;
		if(subs(s[mid])*2>=sum[Root]) k=mid,r=mid-1;
		else l=mid+1;
	}
	return make_pair(subs(s[k]),s[k]);
}
int main(){
	read(n),read(q);
	for(int i=1;i<=n;++i) id[i]=i;
	shuffle(id+1,id+n+1,rnd);
	for(int i=1,k=min(n,(int)sqrt(n));i<=k;++i) mk[id[i]]=1;
	for(int i=1;i<=n;++i){
		read(fa[i]),read(t[i].val);
		if(!fa[i]) Root=i;
		else nxt[i]=head[fa[i]],head[fa[i]]=i;
	}
	mk[Root]=1;
	vector<int> S;
	for(int i=1;i<=n;++i) if(mk[i]) S.push_back(i);

	dfs(Root,0);
	for(int i=1;i<=idx;++i){
		t[xl[i]].pos=rnd();
		while(top&&t[stk[top]].pos>t[xl[i]].pos) t[xl[i]].ls=stk[top],pushup(stk[top--]);
		if(top) t[stk[top]].rs=xl[i];
		stk[++top]=xl[i];
	}
	root=stk[1];
	while(top) pushup(stk[top--]);
	for(int i=1;i<=n;++i) if(sum[i]*2>=sum[Root]&&(!P||sum[i]<sum[P])) P=i;

	print(P),pc('\n');
	int qq=0;
	while(q--){
		int x,y;
		read(x),read(y);++qq;
		x=(x+P)%n+1,y=(y+P)%n+1;
		int fx=find(x),fy=find(y);
		int rk1=qrk(x),rk2=qrk(x+n),rk3=qrk(y);
		if(!mk[x]){
			for(int i:S) if(dfn[i]>=rk1&&dfn[i]<=rk2&&f[i]==fx){
				f[i]=fy;
			}
		}else f[x]=fy;
		fa[x]=y;
		for(int i:S){
			if(rk1<=dfn[i]&&dfn[i]<=rk2){
				if(rk3<rk1) dfn[i]=rk3+dfn[i]-rk1+1;
				else dfn[i]=rk3+dfn[i]-rk1+1-(rk2-rk1+1);
			}else{
				if(rk3<rk1){
					if(dfn[i]>rk3&&dfn[i]<rk1) dfn[i]+=rk2-rk1+1;
				}else{
					if(dfn[i]>rk1&&dfn[i]<=rk3) dfn[i]-=rk2-rk1+1;
				}
			}
		}
		int a,b;
		split(root,a,root,rk1-1);
		split(root,root,b,rk2-rk1+1);
		merge(a,b,a);
		split(a,a,b,qrk(y));
		merge(a,root,root);
		merge(root,b,root);
		pair<int,int> ans=min(query(x),query(P));
		print(P=ans.second),pc('\n');
	}
	flush();
	return 0;
}