Description

給出兩棵 n 結點的有標號樹。
每次操作刪去第一棵樹的一條邊，再加上一條邊，需要保證此時還是一棵樹。
構造一種操作序列，將第一棵樹變成第二棵樹，使得操作數最小。
n ≤ $5\times 10^5$

Solution

• 顯然，對于第一顆樹的邊$x?y$，如果這條邊在第二顆樹中也存在，那么是不可能更改這條邊的。
• 一個樸素的想法是直接遍歷第一顆樹，如果當前節點和其父親連的邊在第二顆樹中沒出現，那么更改為連向第二顆樹中的父節點。
• 但這樣會產生一個問題，如果第二棵樹的父節點在第一顆樹中變成了子節點，那么這條邊也留著，所以不能直接連父節點，否則會出現環
• 考慮把用兩棵樹之間相同的邊連接起來的點縮成一個點，因為兩棵樹都有的邊無需改變，所以我們這樣做對題目沒什么影響
• 我們稱這縮點后的點為大點，可以發現第一棵樹除了根大點外每個大點中深度最低的那個小點與父節點之間的邊是要被改變的，而他們要改成的邊是第二棵樹中這個大點中深度最低的點與父節點之間的邊，所以我們考慮用并查集來做，每個大點即一個并查集，并查集的根為第二棵樹中要改變的點。
• 然后在dfs第一棵樹時，如果遇見不在第二棵樹中的邊，查詢當前節點所在并查集中的根，將第一棵樹中這個節點和父節點之間的邊改成它所在并查集的根與它在第二棵樹中父節點之間的邊。
• 注意：一顆樹中出現環，當且僅當一個點和它父節點連的邊更改成和它的子樹節點連，所以我們從葉子節點往上更新就可以保證不會在操作過程中出現環，即在dfs時要先處理子節點再處理當前節點。

Code

#include<iostream> #include<cstdio> #include<vector> using namespace std; const int N=5e5+5; struct Edge{int v,nxt; }e1[N<<1],e2[N<<1]; int n,head1[N],cnt1,head2[N],cnt2,fa1[N],fa2[N]; int bel[N]; struct Ans{int a,b,c,d;}; vector<Ans> ans; void add1(int u,int v){e1[++cnt1].v=v;e1[cnt1].nxt=head1[u];head1[u]=cnt1; } void add2(int u,int v){e2[++cnt2].v=v;e2[cnt2].nxt=head2[u];head2[u]=cnt2; } void dfs1(int u,int f){for(int i=head1[u];i;i=e1[i].nxt){int v=e1[i].v;if(v==f) continue;fa1[v]=u;dfs1(v,u);} } void dfs2(int u,int f){for(int i=head2[u];i;i=e2[i].nxt){int v=e2[i].v;if(v==f) continue;fa2[v]=u;dfs2(v,u);} } int find(int x){if(bel[x]==x) return x;return bel[x]=find(bel[x]); } void rebuild(int u){for(int i=head1[u];i;i=e1[i].nxt){int v=e1[i].v;if(v==fa1[u]) continue;rebuild(v);if(u!=fa2[v]&&v!=fa2[u])ans.push_back((Ans){u,v,find(v),fa2[find(v)]});} } int main(){scanf("%d",&n);int x,y;for(int i=1;i<n;i++){scanf("%d%d",&x,&y);add1(x,y);add1(y,x);}for(int i=1;i<n;i++){scanf("%d%d",&x,&y);add2(x,y);add2(y,x);}dfs1(1,0);dfs2(1,0);bel[1]=1;for(int i=2;i<=n;i++)bel[i]=(fa1[i]==fa2[i]||fa1[fa2[i]]==i)?fa2[i]:i;rebuild(1);printf("%d\n",ans.size());for(int i=0;i<ans.size();i++) printf("%d %d %d %d\n",ans[i].a,ans[i].b,ans[i].c,ans[i].d);return 0; }

參考文章：
https://blog.csdn.net/u014664226/article/details/50901616

總結

以上是生活随笔為你收集整理的CF650E Clockwork Bomb（树上构造类问题、并查集）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。