专栏文章

CF1137F 题解

llmh_qwq
CF1137F题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min5pczt
此快照首次捕获于
2025/12/01 20:59
3 个月前
此快照最后确认于
2025/12/01 20:59
3 个月前
查看原文
先把无根树转化为有根树，可以令编号最大的点为根——它必定最后被删除。
之后考虑一次查询过程，查询 xx 时找出子树内 pp 最大的节点 yy，显然是 yy 把它卡住了删不掉。之后标记所有 pi≥pyp_i\ge p_y 的节点和其祖先，必定是把树删到只剩下这些节点，然后从 yy 一路删到 xx。
这已经可以处理比较操作了，但为了解决查询操作需要找出所有 pi≥pyp_i\ge p_y 的节点，求包含它们的最小连通块（注意到根节点的 pp 一定 ≥py\ge p_y）的节点数量。
令 11 为根，把所有特殊节点按照 dfs 序排序。之后求出它们的深度之和减去相邻两个位置的 LCA 深度之和，得到的就是包含这些节点和 11 的最小连通块大小；为了去掉根节点的影响，求出所有节点的 LCA（也就是 dfs 序最小和最大的节点的 LCA）即可。
但是我们还需要快速找出这些节点。注意到全程一个 pp 至多出现一次，可以令 aia_i 代表唯一一个存在任意时刻满足 px=ip_x=i 的 xx。
之后找出 pi≥pyp_i\ge p_y 的节点就相当于取出 aa 上面 [py,pr][p_y, p_r] 这一段（rr 为当前 pp 最大的节点）。
现在尝试用莫队维护一个特殊点组成的集合，需要在维护的集合中插入或者删除一个点。求 LCA 可以做到单次 O(1)O(1)，但是在集合中插入删除点需要找到它两侧的第一个点，这需要 O(log⁡n)O(\log n) 的复杂度，无法接受。
利用这个题的技巧，使用只删除的回滚莫队，这样维护一个按照 dfs 序排好序的双向链表，就能直接查询前驱后继。
综上，假设 n,qn,q 同阶，总复杂度 O(nn)O(n\sqrt n)，需要注意算法常数。
CPP
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define lson (u<<1)
#define rson (u<<1|1)
const ll N=200007,B=700;
int n,m,k,nQ,w[N],a[N<<1];
int p[N],dep[N],id[N],tI[N],tO[N],timer,c[N];
int type[N],ans[N],iB[N<<1];
int pre[N],nxt[N],cnt[N],L,R,now;
vector<int> to[N];
char op[10];
struct query{
	int u,l,r,id;
}qry[N<<1];
bool up(int u,int v){
	return tI[u]<=tI[v]&&tO[v]<=tO[u];
}
namespace SGT{
	int pos[N<<2];
	int cmp(int x,int y){return w[x]>w[y]?x:y;}
	void build(int u,int l,int r){
		if (l==r){
			pos[u]=id[l];
			return;
		}
		int mid=l+r>>1;
		build(lson,l,mid);
		build(rson,mid+1,r);
		pos[u]=cmp(pos[lson],pos[rson]);
	}
	void modify(int u,int l,int r,int x){
		if (l==r){
			return;
		}
		int mid=l+r>>1;
		if (x<=mid){
			modify(lson,l,mid,x);
		}
		else{
			modify(rson,mid+1,r,x);
		}
		pos[u]=cmp(pos[lson],pos[rson]);
	}
	int query(int u,int l,int r,int L,int R){
		if (L<=l&&r<=R){
			return pos[u];
		}
		int mid=l+r>>1;
		if (R<=mid){
			return query(lson,l,mid,L,R);
		}
		if (L>mid){
			return query(rson,mid+1,r,L,R);
		}
		return cmp(query(lson,l,mid,L,R),query(rson,mid+1,r,L,R));
	}
}
namespace ST{
	int mn[20][N],st[20][N];
	int cmp(int x,int y){
		return dep[x]<dep[y]?x:y;
	}
	void build(){
		for (int i=1;i<=n;++i){
			mn[0][i]=id[i];
			st[0][i]=dep[id[i]];
		}
		for (int p=1;p<20;++p){
			for (int i=1;i<=n-(1<<p)+1;++i){
				mn[p][i]=cmp(mn[p-1][i],mn[p-1][i+(1<<p-1)]);
				st[p][i]=min(st[p-1][i],st[p-1][i+(1<<p-1)]);
			}
		}
	}
	int query(int l,int r){
		int k=__lg(r-l+1);
		return cmp(mn[k][l],mn[k][r-(1<<k)+1]);
	}
	int query_dep(int l,int r){
		int k=__lg(r-l+1);
		return min(st[k][l],st[k][r-(1<<k)+1]);
	}
}
int LCA(int u,int v){
	if (u==v){
		return u;
	}
	if (tI[u]>tI[v]){
		return p[ST::query(tI[v]+1,tI[u])];
	}
	return p[ST::query(tI[u]+1,tI[v])];
}
int get_max_value(int root,int u){
	if (up(u,root)){
		u=ST::query(tI[u]+1,tI[root]);
		if (tO[u]==n){
			return SGT::query(1,1,n,1,tI[u]-1);
		}
		return SGT::cmp(SGT::query(1,1,n,1,tI[u]-1),SGT::query(1,1,n,tO[u]+1,n));
	}
	return SGT::query(1,1,n,tI[u],tO[u]);
}
int dis(int u,int v){
	return dep[u]+dep[v]-2*dep[LCA(u,v)];
}
void dfs(int u,int fa){
	p[u]=fa;dep[u]=dep[fa]+1;tI[u]=++timer;id[timer]=u;
	for (auto v:to[u]){
		if (v==fa){
			continue;
		}
		dfs(v,u);
	}
	tO[u]=timer;
}
namespace SGT2{
	ll val[N<<3];
	void build(int u,int l,int r){
		if (l==r){
			val[u]=dep[LCA(a[l-1],a[l])]-1;
			return;
		}
		int mid=l+r>>1;
		build(lson,l,mid);build(rson,mid+1,r);
		val[u]=min(val[lson],val[rson]);
	}
	int query(int u,int l,int r,int L,int R){
		if (L<=l&&r<=R){
			return val[u];
		}
		int mid=l+r>>1;
		if (R<=mid){
			return query(lson,l,mid,L,R);
		}
		if (L>mid){
			return query(rson,mid+1,r,L,R);
		}
		return min(query(lson,l,mid,L,R),query(rson,mid+1,r,L,R));
	}
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	k=n;
	for (int u,v,i=1;i<n;++i){
		cin>>u>>v;
		to[u].emplace_back(v);to[v].emplace_back(u);
	}
	dfs(1,0);
	ST::build();
	for (int i=1;i<=n;++i){
		w[i]=a[i]=i;c[i]=1;
	}
	SGT::build(1,1,n);
	auto add_query=[&](int u,int id){
		if (u==a[k]){
			ans[id]=n;
			return;
		}
		int v=get_max_value(a[k],u);
		qry[++nQ]=(query){u,w[v],k,id};
		ans[id]=n+dis(u,v)+1;
	};
	for (int u,v,i=1;i<=m;++i){
		cin>>op;
		type[i]=op[0];
		if (op[0]=='u'){
			cin>>u;
			a[++k]=u;++c[u];
			w[u]=k;
			SGT::modify(1,1,n,tI[u]);
		}
		else if (op[0]=='w'){
			cin>>u;
			add_query(u,i);
		}
		else{
			cin>>u>>v;
			if (u==a[k]||v==a[k]){
				ans[i]=u^v^a[k];
			}
			else{
				int U=get_max_value(a[k],u),V=get_max_value(a[k],v);
				if (U!=V){
					ans[i]=(w[U]<w[V]?u:v);
				}
				else{
					ans[i]=(dis(u,U)<dis(v,V)?u:v);
				}
			}
		}
	}
	for (int l=1,r,o=0;l<=k;l=r+1){
		r=min(k,l+B-1);
		++o;
		for (int i=l;i<=r;++i){
			iB[i]=o;
		}
	}
	sort(qry+1,qry+1+nQ,[&](const query& a,const query& b){
		return iB[a.l]==iB[b.l]?a.r>b.r:a.l<b.l;
	});
	auto del=[&](const int& x){
		if (--cnt[x]){
			return;
		}
		int l=pre[x],r=nxt[x];
		nxt[l]=r;pre[r]=l;
		now-=dep[id[x]]+ST::query_dep(l+1,r)-ST::query_dep(l+1,x)-ST::query_dep(x+1,r)+1;
	};
	auto add=[&](const int& x){
		if ((++cnt[x])==1){
			nxt[pre[x]]=pre[nxt[x]]=x;
		}
	};
	now=n;L=1;R=k;
	int A=n;
	for (int i=1;i<=n;++i){
		cnt[i]=c[id[i]];
		pre[i]=i-1;nxt[i]=i+1;
	}
	SGT2::build(1,2,k);
	for (int t=1;t<=nQ;++t){
		if (iB[qry[t].l]!=iB[qry[t-1].l]){
//			cerr<<iB[qry[t].l]<<' '<<t<<endl;
			now=A;
			while(R<k){
				add(tI[a[++R]]);
			}
			while(iB[L]!=iB[qry[t].l]){
				del(tI[a[L++]]);
			}
			A=now;
		}
		while(R>qry[t].r){
			del(tI[a[R--]]);
		}
		int tnow=now,tl=L;
		while(L<qry[t].l){
			del(tI[a[L++]]);
		}
		ans[qry[t].id]-=now-SGT2::query(1,2,k,qry[t].l+1,qry[t].r);
		while(L>tl){
			add(tI[a[--L]]);
		}
		now=tnow;
	}
	for (int i=1;i<=m;++i){
		if (type[i]=='w'||type[i]=='c'){
			cout<<ans[i]<<'\n';
		}
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...