专栏文章

P12403 题解

DDaiRuiChen007
P12403题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@mimz28x5
此快照首次捕获于
2025/12/01 17:53
3 个月前
此快照最后确认于
2025/12/01 17:53
3 个月前
查看原文
Problem Link
首先树上 s,ts,t 距离 >2>2 那么可以相向移动，所以只要暴力枚举距离 ≤2\le 2 的点对。
对于基环树上的问题，类似地如果 s,ts,t 都不在环上，则只要考虑距离 ≤2\le 2 的情况。
否则我们只要考虑存在一个不完全同色的环的情况。
枚举该环，必定有一个点在环上，设为 ss，则分讨环上是否有黑色点。
如果有，则粉点和黑点都是区间，且两个区间中间夹了 ≤1\le 1 个蓝色点。
枚举粉色区间后只有 O(n)\mathcal O(n) 种要检验的区间对，我们要在长度较小的区间上任意一个点的子树中找到深度为 12\frac 12 区间长度差的点。
那么换根 dp 求仙人掌上每个点子树内外最大深度，然后单调队列维护区间最深点即可判断。
如果没有黑点，则蓝点和黑点都是区间，且粉点一定是蓝点区间两个端点的某个子树，枚举该子树并算出黑点范围，然后要在该子树中找深度为某个值的点，依然可以预处理。
时间复杂度 O(n+m)\mathcal O(n+m)。
代码：
CPP
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=4e5+5;
vector <int> G[MAXN],E[MAXN];
int n,m,vc,A,B,dfn[MAXN],low[MAXN],dcnt,st[MAXN],tp;
bool ins[MAXN];
void tarjan(int u) {
	dfn[u]=low[u]=++dcnt,ins[st[++tp]=u]=1;
	for(int v:E[u]) {
		if(!dfn[v]) {
			tarjan(v),low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]) {
				for(G[u].push_back(++vc);ins[v];ins[st[tp--]]=0) G[vc].push_back(st[tp]);
			}
		} else low[u]=min(low[u],dfn[v]);
	}
}
int siz[MAXN],fa[MAXN],c[MAXN],f[MAXN];
void dfs1(int u,int fz) {
	siz[u]=u<=n,fa[u]=fz;
	for(int v:G[u]) dfs1(v,u),siz[u]+=siz[v];
	if(u<=n) for(int v:G[u]) f[u]=max(f[u],f[v]);
	else {
		c[u]=G[u].size()+1;
		for(int i=0;i<c[u]-1;++i) f[u]=max(f[u],f[G[u][i]]+min(i+1,c[u]-1-i));
	}
}
int g[MAXN],q[MAXN],w[MAXN];
void dfs2(int u) {
	if(u<=n) {
		int fi=g[u],se=0;
		for(int v:G[u]) se=max(se,min(fi,f[v])),fi=max(fi,f[v]);
		for(int v:G[u]) g[v]=(f[v]==fi?se:fi);
	} else {
		w[c[u]-1]=g[u];
		for(int i=0;i<c[u]-1;++i) w[i]=w[i+c[u]]=f[G[u][i]];
		int hd=1,tl=0,d=c[u]/2;
		for(int o=2;o--;) {
			for(int i=0;i<2*c[u]-1;++i) {
				while(hd<=tl&&q[hd]<i-d) ++hd;
				if(i>=c[u]) g[G[u][i-c[u]]]=max(g[G[u][i-c[u]]],i-q[hd]+w[q[hd]]);
				while(hd<=tl&&w[q[tl]]-q[tl]<=w[i]-i) --tl;
				q[++tl]=i;
			}
			reverse(w,w+2*c[u]-1),reverse(G[u].begin(),G[u].end());
		}
	}
	for(int v:G[u]) dfs2(v);
}
vector <int> H[MAXN];
int d[MAXN],b[MAXN],pa[MAXN],pb[MAXN],xa[MAXN],xb[MAXN];
ll s[MAXN];
bool vis[MAXN];
int in(int x,int e) {
	queue <array<int,2>> Q; Q.push({x,0});
	while(1) {
		auto u=Q.front(); Q.pop();
		if(u[1]==e) return u[0];
		for(int v:E[u[0]]) if(!vis[v]) vis[v]=true,Q.push({v,u[1]+1});
	}
}
void solve() {
	cin>>n>>m>>A>>B,vc=n;
	for(int i=1,u,v;i<=m;++i) cin>>u>>v,E[u].push_back(v),E[v].push_back(u);
	tarjan(1),dfs1(1,0);
	for(int u=1;u<=n;++u) {
		if(!fa[u]||G[fa[u]].size()>1) continue;
		if(siz[u]==A&&n-siz[u]==B) return cout<<u<<" "<<fa[fa[u]]<<"\n",void();
		if(siz[u]==B&&n-siz[u]==A) return cout<<fa[fa[u]]<<" "<<u<<"\n",void();
	}
	for(int u=1;u<=n;++u) {
		if(fa[u]&&G[fa[u]].size()==1) H[n-siz[u]].push_back(fa[fa[u]]);
		for(int v:G[u]) if(G[v].size()==1) H[siz[v]].push_back(G[v][0]);
		if(A==B&&H[A].size()>1) return cout<<H[A][0]<<" "<<H[A][1]<<"\n",void(); 
		if(A!=B&&H[A].size()&&H[B].size()) return cout<<H[A][0]<<" "<<H[B][0]<<"\n",void();
		H[n-siz[u]].clear();
		for(int v:G[u]) H[siz[v]].clear();
	}
	dfs2(1);
	for(int u=n+1;u<=vc;++u) if(G[u].size()>1) {
		for(int i=0;i<c[u]-1;++i) s[i+1]=s[i+c[u]+1]=siz[G[u][i]],d[i+1]=d[i+c[u]+1]=f[G[u][i]],b[i+1]=b[i+c[u]+1]=G[u][i];
		s[c[u]]=s[2*c[u]]=n-siz[u],d[c[u]]=d[2*c[u]]=g[u],b[0]=b[c[u]]=b[2*c[u]]=fa[u];
		for(int i=1;i<=2*c[u];++i) s[i]+=s[i-1],pa[i]=pb[i]=xa[i]=xb[i]=0;
		for(int i=1,j=1,k=1;i<=c[u];++i) {
			while(s[j]-s[i-1]<A) ++j;
			while(s[k]-s[i-1]<B) ++k;
			if(s[j]-s[i-1]==A) pa[i]=j;
			if(s[k]-s[i-1]==B) pb[i]=k;
		}
		for(int i=2*c[u],j=i,k=i;i>c[u];--i) {
			while(s[i]-s[j-1]<A) --j;
			while(s[i]-s[k-1]<B) --k;
			if(s[i]-s[j-1]==A) pa[i]=j;
			if(s[i]-s[k-1]==B) pb[i]=k;
		}
		for(int i=2*c[u],hd=1,tl=0;i;--i) {
			while(hd<=tl&&d[q[tl]]<=d[i]) --tl;
			q[++tl]=i;
			if(i<=c[u]&&pa[i]) {
				while(hd<=tl&&q[hd]>pa[i]) ++hd;
				xa[i]=q[hd];
			}
		}
		for(int i=2*c[u],hd=1,tl=0;i;--i) {
			while(hd<=tl&&d[q[tl]]<=d[i]) --tl;
			q[++tl]=i;
			if(i<=c[u]&&pb[i]) {
				while(hd<=tl&&q[hd]>pb[i]) ++hd;
				xb[i]=q[hd];
			}
		}
		for(int i=1;i<=c[u];++i) if(pa[i]) {
			auto chk=[&](int lx,int rx,int ly,int ry) {
				if(ly>ry) return 0;
				if(ly>c[u]) ly-=c[u],ry-=c[u];
				if(s[ry]-s[ly-1]!=B) return 0;
				int dx=rx-lx+1,dy=ry-ly+1;
				if(dx%2!=dy%2) return 0;
				int k=(dx-dy)/2;
				if(k>0) {
					if(d[xb[ly]]<k) return 0;
					for(int x=1;x<=c[u];++x) vis[b[x]]=1;
					cout<<b[lx+ry-xb[ly]+k]<<" "<<in(b[xb[ly]],k)<<"\n";
					return 1;
				} else {
					if(d[xa[lx]]<-k) return 0;
					for(int x=1;x<=c[u];++x) vis[b[x]]=1;
					cout<<in(b[xa[lx]],-k)<<" "<<b[ly+rx-xa[lx]-k]<<"\n";
					return 1;
				}
			};
			for(int l:{pa[i]+1,pa[i]+2}) for(int r:{i+c[u]-2,i+c[u]-1}) if(chk(i,pa[i],l,r)) return ;
		}
		auto chk=[&](int x,int up,int l,int r,int o) {
			if(!l||!r) return 0;
			if(r-l+1>=c[u]||r-l+1<(c[u]+1)/2) return 0;
			int t=r-l+1-(c[u]+1)/2;
			if(t>up) return 0;
			for(int i=1;i<=c[u];++i) vis[b[i]]=1;
			vis[x]=1;
			int y=in(x,t),z=(o&2?b[r-t]:b[l+t]);
			if(o&1) swap(y,z);
			cout<<y<<" "<<z<<"\n";
			return 1;
		};
		for(int i=1;i<=c[u];++i) for(int x:G[b[i]]) if(G[x].size()==1) {
			int j=(i<c[u]?i+1:1),k=(i>1?i+c[u]-1:2*c[u]);
			if(siz[x]==A&&chk(G[x][0],f[x]-1,j,pb[j],0)) return ;
			if(siz[x]==B&&chk(G[x][0],f[x]-1,j,pa[j],1)) return ;
			if(siz[x]==A&&chk(G[x][0],f[x]-1,pb[k],k,2)) return ;
			if(siz[x]==B&&chk(G[x][0],f[x]-1,pa[k],k,3)) return ;
		}
		if(fa[fa[u]]&&G[fa[fa[u]]].size()==1) {
			int x=fa[fa[u]];
			if(n-siz[x]==A&&chk(fa[x],g[x],1,pb[1],0)) return ;
			if(n-siz[x]==B&&chk(fa[x],g[x],1,pa[1],1)) return ;
			if(n-siz[x]==A&&chk(fa[x],g[x],pb[2*c[u]-1],2*c[u]-1,2)) return ;
			if(n-siz[x]==B&&chk(fa[x],g[x],pa[2*c[u]-1],2*c[u]-1,3)) return ;
		}
	}
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int _; cin>>_;
	while(_--) {
		solve(),dcnt=tp=0;
		for(int i=0;i<=2*n;++i) {
			G[i].clear(),E[i].clear(),H[i].clear();
			dfn[i]=low[i]=st[i]=ins[i]=0;
			siz[i]=fa[i]=c[i]=f[i]=g[i]=q[i]=w[i]=0;
			d[i]=b[i]=s[i]=pa[i]=pb[i]=xa[i]=xb[i]=vis[i]=0;
		}
	}
	return 0;
}

评论

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

正在加载评论...