P12403 题解

· · 题解

Problem Link

首先树上 s,t 距离 >2 那么可以相向移动，所以只要暴力枚举距离 \le 2 的点对。

对于基环树上的问题，类似地如果 s,t 都不在环上，则只要考虑距离 \le 2 的情况。

否则我们只要考虑存在一个不完全同色的环的情况。

枚举该环，必定有一个点在环上，设为 s，则分讨环上是否有黑色点。

如果有，则粉点和黑点都是区间，且两个区间中间夹了 \le 1 个蓝色点。

枚举粉色区间后只有 \mathcal O(n) 种要检验的区间对，我们要在长度较小的区间上任意一个点的子树中找到深度为 \frac 12 区间长度差的点。

那么换根 dp 求仙人掌上每个点子树内外最大深度，然后单调队列维护区间最深点即可判断。

如果没有黑点，则蓝点和黑点都是区间，且粉点一定是蓝点区间两个端点的某个子树，枚举该子树并算出黑点范围，然后要在该子树中找深度为某个值的点，依然可以预处理。

时间复杂度 \mathcal O(n+m)。

代码：

#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;
}