题解 AT2377 【Blue and Red Tree】
大菜鸡fks
2018-10-17 16:02:31
首先可以发现最终状态替换的红边和蓝边一定是重边。把这条边两端的联通块看成一个点。
往回推，要形成这两个点，必须也要有类似的重边。
这样就可以得到一种做法。每次把重边两端的放入队列，并把边集合并（启发式合并），把这两个联通块合并
再把重边放入，直至更新完成
```cpp
#include<cstdio>
#include<set>
#include<map>
#include<algorithm>
#define mp(x,y) make_pair(x,y)
#define pi pair<int,int>
using namespace std;
inline int read(){int x=0,f=1,ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}
inline void write(int x){if (x<0) putchar('-'),x=-x; if (x>=10) write(x/10); putchar(x%10+'0');}
inline void writeln(int x){write(x); puts("");}
const int N=1e5+5;
set<int >se[N];
map<pi,int> ma;
pi q[N];
int n,h,t,fa[N];
inline int getfa(int x){
return (fa[x]==x)?x:fa[x]=getfa(fa[x]);
}
inline void init(){
n=read();
for (int i=1;i<=n*2-2;i++){
int u=read(),v=read();
se[u].insert(v); se[v].insert(u);
ma[mp(u,v)]++; ma[mp(v,u)]++;
if (ma[mp(u,v)]==2) q[++t]=make_pair(u,v);
}
}
inline void solve(){
for (int i=1;i<=n;i++) fa[i]=i;
set<int >::iterator it;
while (h<t){
int u=q[++h].first,v=q[h].second;
u=getfa(u); v=getfa(v);
se[u].erase(v); se[v].erase(u);
if (se[u].size()<se[v].size()) swap(u,v);
for (it=se[v].begin();it!=se[v].end();++it){
int to=(*it);
ma[mp(to,v)]=ma[mp(v,to)]=0;
se[to].erase(v); se[to].insert(u);
ma[mp(to,u)]++; ma[mp(u,to)]++;
if (ma[mp(to,u)]==2) q[++t]=make_pair(to,u);
se[u].insert(to);
}
fa[v]=u;
se[v].clear();
}
int s=0;
for (int i=1;i<=n;i++) s+=fa[i]==i;
if (s==1) puts("YES"); else puts("NO");
}
int main(){
init(); solve();
return 0;
}
```