本文主要是介绍【luogu AT2377】Blue and Red Tree（思维）（STL）（启发式合并），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Blue and Red Tree

题目链接：luogu AT2377

题目大意

给你一棵树，每次你可以选一条路径，删掉其中的一条边，然后把路径两断点编号在另一个一样点数的图上连边。
然后给你一个要求的树形态，问你是否有方案能让你连出要求的树。

思路

发现不太能下手，考虑一些至少有的条件。
发现至少要有边重合，因为你至少最后一步是图上剩下两个一样的边，然后连。

于是考虑反着来？
每次连好边之后，假设 \(2,3\) 连边了。
那两个图分别是 \(1,2\) 和 \(1,3\)，那你可以通过 \(2,3\) 找到 \(1,2,3\) 的路径，从而使得 \(1,3\) 连边。
某种意义上来讲，你既然连边就相当于你可以从这个点集的任意一个点走到任意一个点，而且形成一条路径，所以你就可以把它相当于缩点！

那考虑怎么找两个一样的边。
发现每次暴力判断每个复杂度不行，考虑维护两点之间的边数。
那连边涉及到合并，所以你用个启发式合并，把 \(y\) 连着的点之间的边删掉，改为跟 \(x\) 连。

然后发现可能会有重边（就是重复统计），所以你要记得判一下之类的。
然后就好了，如果没有一样的边了树还没弄好就是 NO，否则就是 YES。

代码

#include<set>
#include<map>
#include<cstdio>
#include<algorithm>

using namespace std;

const int N = 1e6 + 100;
int n, l, r;
multiset <int> G[N];
map <pair <int, int>, int> mp;
pair <int, int> xl[N];

void add(int x, int y) {
	if (x > y) swap(x, y);
	if (x == y) return ;//小心自环，可以说是每次合并应该必有的
	mp[make_pair(x, y)]++;
	if (mp[make_pair(x, y)] == 2) {
		xl[++r] = make_pair(x, y);
	}
	G[x].insert(y); G[y].insert(x);
}

void del(int x, int y) {
	if (x > y) swap(x, y); mp[make_pair(x, y)] = 0;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= 2 * n - 2; i++) {
		int x, y; scanf("%d %d", &x, &y);
		add(x, y);
	}
	
	int cnt = 0;
	while (++cnt <= n - 1) {
		if (l >= r) {
			printf("NO"); return 0;
		}
		l++; int x = xl[l].first, y = xl[l].second;
		if (!mp[xl[l]]) {cnt--; continue;}
		if (G[x].size() < G[y].size()) swap(x, y);
		for (multiset <int> ::iterator it = G[y].begin(); it != G[y].end(); it++) {
			int z = *it;
			del(y, z); G[z].erase(G[z].find(y));
			add(x, z);
		}
		G[y].clear();
	}
	printf("YES");
	
	return 0;
}

这篇关于【luogu AT2377】Blue and Red Tree（思维）（STL）（启发式合并）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！