Submission #1768878

---

Source Code Expand

#include <bits/stdc++.h>
#define xx first
#define yy second
#define mp make_pair
#define pb push_back
#define mset(x, y) memset(x, y, sizeof x)
#define mcpy(x, y) memcpy(x, y, sizeof x)
using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

inline int Read()
{
	int x = 0, f = 1, c = getchar();
	for (; !isdigit(c); c = getchar())
		if (c == '-')
			f = -1;
	for (;  isdigit(c); c = getchar())
		x = x * 10 + c - '0';
	return x * f;
}

const int MAXN = 100005;

multiset <int> adj[MAXN];
map <pii, int> cnt, use;
int n, f[MAXN];
queue <pii> q;

inline pii Mak(int x, int y)
{
	return x < y ? mp(x, y) : mp(y, x);
}

inline int Find(int x)
{
	while (x ^ f[x])
		x = f[x] = f[f[x]];
	return x;
}

int main()
{
#ifdef wxh010910
	freopen("data.in", "r", stdin);
#endif
	n = Read();
	for (int i = 1; i <= n; i ++)
		f[i] = i;
	for (int i = 1, x, y; i <= n - 1 << 1; i ++)
	{
		x = Read(), y = Read();
		adj[x].insert(y), adj[y].insert(x);
		if (cnt[Mak(x, y)] ++ && use.find(Mak(x, y)) == use.end())
			q.push(Mak(x, y)), use[Mak(x, y)] = 1;
	}
	for (int i = 1, x, y; i < n; i ++)
	{
		do
		{
			if (q.empty())
				return puts("NO"), 0;
			x = Find(q.front().xx), y = Find(q.front().yy), q.pop();
		} while (x == y);
		if (adj[x].size() > adj[y].size())
			swap(x, y);
		f[x] = y;
		for (auto z : adj[x])
		{
			z = Find(z);
			if (z == y)
				continue;
			adj[y].insert(z), adj[z].insert(y);
			if (cnt[Mak(y, z)] ++ && use.find(Mak(y, z)) == use.end())
				q.push(Mak(y, z)), use[Mak(y, z)] = 1;
			adj[z].erase(adj[z].find(x));
		}
		adj[y].erase(adj[y].find(x)), adj[x].clear();
	}
	return puts("YES"), 0;
}

Submission Info

Judge Result