题目描述
有一棵
n
个点的树，最开始所有边都是蓝边。每次你可以选择一条全是蓝边的路径，删掉其中一条，再把这两个端点之间连一条红边。再给你一棵树，这棵树的所有边都是红边，问你最终能不能把原来的树变成这棵新树。
n≤100000
题解
考虑最后一条加的边，那么当前也有一条相同的蓝边。也就是说，如果把这两棵树合在一起，这两个点之间会有两条边。然后可以把这两个点缩成一个点。
所以我们每次选择之间有两条边的一对点，把这两个点合在一起。可以直接遍历度数较小的那个点
x
相邻的边，把这条边的另一个端点v向度数较大的那个点
y
连边。顺便用并查集维护每个点缩点之后是什么点。
时间复杂度：O(nlog2n)
代码
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#include<utility>
#include<map>
#include<queue>
#include<set>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<
int,
int> pii;
int n;
map<ll,int> a;
queue<pii> q;
set<int> l[
100010];
int f[
100010];
int find(
int x)
{
return f[x]==x?x:f[x]=find(f[x]);
}
ll getid(
int x,
int y)
{
if(x>y)
swap(x,y);
return ll(x)*n+y;
}
void link(
int x,
int y)
{
l[x].insert(y);
l[y].insert(x);
ll v=getid(x,y);
a[v]++;
if(a[v]==
3)
{
printf(
"NO\n");
exit(
0);
}
if(a[v]==
2)
q.push(pii(x,y));
}
int main()
{
#ifdef DEBUG
freopen(
"b.in",
"r",stdin);
freopen(
"b.out",
"w",stdout);
#endif
scanf(
"%d",&n);
int i,x,y;
for(i=
1;i<=
2*n-
2;i++)
{
scanf(
"%d%d",&x,&y);
link(x,y);
}
for(i=
1;i<=n;i++)
f[i]=i;
for(i=
1;i<n;i++)
{
while(
1)
{
if(q.empty())
{
printf(
"NO\n");
return 0;
}
x=q.front().first;
y=q.front().second;
q.pop();
if(x!=y)
break;
}
if(l[x].size()>l[y].size())
swap(x,y);
f[x]=y;
a.erase(getid(x,y));
l[y].erase(x);
for(
auto v:l[x])
{
v=find(v);
if(v==y)
continue;
a.erase(getid(x,v));
link(v,y);
l[v].erase(x);
l[x].erase(v);
}
}
printf(
"YES\n");
return 0;
}
