正题

题目链接:https://www.luogu.com.cn/problem/AT2377

---

题目大意

有两棵树$T_1,T_2$。$T_1$树上的边开始时都是蓝色的，我们每次选择一条蓝色边路径$(x,y)$，然后删掉路径上一条边，连接一条$x$到$y$的红色边。

要求最后所有都是红色边的情况下能不能变成$T_2$。

$1\le n\le 10^5$

---

解题思路

考虑反过来，所以开始时视$T_1$上没有边，我们从$T_2$开始考虑，对于每一条$(x,y)$它合法的时机当且仅当$T_1$中$x,y$的路径上只剩下一条边没有补上。

所以这个时候我们直接选择这条路径补上这条边一定是对的，因为如果被其他的补上了就不合法，而它也只会补上这条边。

此时我们的方案就唯一了，实现的时候我们可以每次找到一条两棵树上都有的边$(x,y)$，然后将节点$x$和节点$y$合并，我们用set来记录每个点连出去的边，合并的时候就启发式合并就好了。

时间复杂度：$O(n{\log }^{2}n)$

---

code

#include
#include
#include
#include
#include
#include
#define mp(x,y) make_pair(x,y)
using namespace std;
const int N=1e5+10;
int n;multiset<int> s[N];
queue<pair<int,int> > q;
map<int,int> mp[N];
void addl(int x,int y){
	if(x==y)return;
	if(x>y)swap(x,y);mp[x][y]++;
	s[x].insert(y);s[y].insert(x);
	if(mp[x][y]==2)q.push(mp(x,y));
	return;
}
int main()
{
	scanf("%d",&n);
	for(int i=1,x,y;i<2*n-1;i++)
		scanf("%d%d",&x,&y),addl(x,y);
	while(!q.empty()){
		int x=q.front().first,y=q.front().second;
		q.pop();if(!mp[x][y])continue;
		if(s[x].size()<s[y].size())swap(x,y);
		while(!s[y].empty()){
			int z=*s[y].begin();
			mp[min(z,y)][max(z,y)]=0;
			s[z].erase(s[z].find(y));
			s[y].erase(s[y].begin());
			addl(x,z);
		}
		n--;
	}
	if(n==1)puts("YES");
	else puts("NO");
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41