题解：P10683 [COTS 2024] 划分 Particija
LastKismet · · 题解
先考虑原问题。
你考虑对每个点，两个划分中都有唯一一个包含它的，那么必须从二者中选出一个。可以建出二分图，对每个连通块取左右部点较小值即可。
考虑最小化答案。
我们发现我们需要分裂原连通块，而只要改的那一条边不是连接的两个孤点，存在方案将之连向一侧的连通块内部消除其影响，否则存在方案将其中一点加入某连通块较大一侧亦无影响，除非
考虑最大化答案。
我们发现我们需要合并原连通块，考虑如何选定最优连边对象，对一个左部点更少的块，我们会选定一个左部点更多的块与其相连，直接用左减右最大的块与其进行判定即可，反之同理。倘若选定的边是割边，先求出断边影响然后分别尝试为分出的两个块连边即可。
const int N=2e5+5,NN=N<<1;;
int n,nn;
int a[N],b[N];
namespace __0{
int fa[NN<<1],sz[NN<<1];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void merge(int a,int b){a=find(a),b=find(b);if(a!=b)fa[a]=b,sz[b]+=sz[a];}
bool same(int a,int b){return find(a)==find(b);}
void solve(){
nn=n<<1;
rep(i,1,n)b[i]+=n;
rep(i,1,nn<<1)sz[i]=i<=nn,fa[i]=i;
rep(i,1,n)merge(a[i],b[i]+nn),merge(a[i]+nn,b[i]);
int ans=0;
rep(i,1,nn)if(fa[i]==i)ans+=min(sz[i],sz[i+nn]);
put(ans);
}
}
int ecnt,hd[NN],ne[NN],to[NN];
il void adde(int a,int b){ne[ecnt]=hd[a],to[ecnt]=b,hd[a]=ecnt++;}
int dfn[NN],low[NN],dcnt;
int scnt,scc[NN],stk[NN],top;
int sz1[NN],sz2[NN];
void tarjan(int x,int fe){
dfn[x]=low[x]=++dcnt;
stk[++top]=x;
for(int e=hd[x];~e;e=ne[e])if(e!=(fe^1)){
int y=to[e];
if(!dfn[y])tarjan(y,e),chmin(low[x],low[y]);
else chmin(low[x],dfn[y]);
}
if(low[x]>=dfn[x]){
++scnt;
while(1){
int u=stk[top--];
scc[u]=scnt;
if(u==x)break;
}
}
}
int bas,ans;
bool vis[NN];
vec<int> g[NN];
namespace __1{
void dfs0(int x,int fa=0){
vis[x]=1;
for(auto y:g[x])if(y!=fa)dfs0(y,x),sz1[x]+=sz1[y],sz2[x]+=sz2[y];
}
void dfs(int x,int fa,int gr){
for(auto y:g[x])if(y!=fa)
dfs(y,x,gr),chmin(ans,-min(sz1[gr],sz2[gr])+min(sz1[y],sz2[y])+min(sz1[gr]-sz1[y],sz2[gr]-sz2[y]));
}
void solve(){
if(n==1)return put(1);
nn=n<<1;
ecnt=0;rep(i,1,nn)hd[i]=-1;
rep(i,1,n)adde(a[i],b[i]+n),adde(b[i]+n,a[i]);
dcnt=scnt=0;rep(i,1,nn)dfn[i]=0;
rep(i,1,nn)if(!dfn[i])tarjan(i,ecnt);
rep(i,1,scnt)sz1[i]=sz2[i]=0;
rep(i,1,nn)++(i<=n?sz1:sz2)[scc[i]];
rep(i,1,scnt)g[i].clear(),vis[i]=0;
rep(x,1,nn)for(int e=hd[x];~e;e=ne[e]){int y=to[e];if(scc[y]!=scc[x])g[scc[x]].pub(scc[y]);}
ans=0,bas=0;
rep(i,1,scnt)if(!vis[i])dfs0(i),bas+=min(sz1[i],sz2[i]),dfs(i,0,i);
put(bas+ans);
}
}
namespace __2{
bool pd[NN];
void dfs0(int x,int fa=0){
vis[x]=1;
for(auto y:g[x])if(y!=fa)dfs0(y,x),sz1[x]+=sz1[y],sz2[x]+=sz2[y],pd[x]|=pd[y];
}
set<pii> st;
void work(int s1,int s2,int d=0,int tv=0){
if(s1==s2)return;
auto [v,y]=(s1<s2?*st.rbegin():*st.begin());
if(y==d)tie(v,y)=(s1<s2?*++st.rbegin():*++st.begin());
chmax(ans,-min(s1,s2)-min(sz1[y],sz2[y])+min(s1+sz1[y],s2+sz2[y])+tv);
}
void dfs(int x,int fa,int gr){
for(auto y:g[x])if(y!=fa){
int tv=-min(sz1[gr],sz2[gr])+min(sz1[y],sz2[y])+min(sz1[gr]-sz1[y],sz2[gr]-sz2[y]);
dfs(y,x,gr),work(sz1[y],sz2[y],gr,tv),work(sz1[gr]-sz1[y],sz2[gr]-sz2[y],gr,tv);
}
}
void solve(){
if(n==1)return put(1);
nn=n<<1;
ecnt=0;rep(i,1,nn)hd[i]=-1;
rep(i,1,n)adde(a[i],b[i]+n),adde(b[i]+n,a[i]);
dcnt=scnt=0;rep(i,1,nn)dfn[i]=0;
rep(i,1,nn)if(!dfn[i])tarjan(i,ecnt);
rep(i,1,scnt)sz1[i]=sz2[i]=0;
rep(i,1,nn)++(i<=n?sz1:sz2)[scc[i]];
rep(i,1,scnt)g[i].clear(),vis[i]=0,pd[i]=0;
rep(x,1,nn)for(int e=hd[x];~e;e=ne[e]){int y=to[e];if(scc[y]!=scc[x])g[scc[x]].pub(scc[y]);else pd[scc[x]]=1;}
ans=0,bas=0;
vec<int> rts;st.clear();
rep(i,1,scnt)if(!vis[i])dfs0(i),bas+=min(sz1[i],sz2[i]),rts.pub(i),st.insert({sz1[i]-sz2[i],i});
if(st.begin()->fir<=0&&st.rbegin()->fir<=0||st.begin()->fir>=0&&st.rbegin()->fir>=0)return put(bas);
for(auto x:rts)if(sz1[x]!=sz2[x])
if(pd[x])work(sz1[x],sz2[x]);
else dfs(x,0,x);
put(bas+ans);
}
}
void INIT(){}
void MAIN(int K){
read(n);
rep(i,1,n)read(a[i]);
rep(i,1,n)read(b[i]);
if(K==0)return __0::solve();
else if(K==1)return __1::solve();
else return __2::solve();
}