Submission #1610097

---

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;
const int INF = 0x3f3f3f3f;
 
int n, tim, dfn[MAXN], dep[MAXN], par[MAXN], bel[MAXN], siz[MAXN];
set <pii> S[MAXN << 2];
vector <int> adj[MAXN];
pii mn[MAXN << 2];

inline void Dfs(int x)
{
	siz[x] = 1;
	for (auto y : adj[x])
		if (y ^ par[x])
			par[y] = x, dep[y] = dep[x] + 1, Dfs(y), siz[x] += siz[y];
}

inline void Dfs(int x, int c)
{
	dfn[x] = ++ tim, bel[x] = c;
	int k = 0;
	for (auto y : adj[x])
		if (y ^ par[x])
			if (siz[y] > siz[k])
				k = y;
	if (!k)
		return ;
	Dfs(k, c);
	for (auto y : adj[x])
		if (y ^ par[x])
			if (y ^ k)
				Dfs(y, y);
}

inline void Pushup(int x)
{
	mn[x] = min(mn[x << 1], mn[x << 1 | 1]);
	mn[x].xx += S[x].size();
}

inline void Build(int x, int l, int r)
{
	mn[x].yy = l;
	if (l == r)
		return ;
	int mid = l + r >> 1;
	Build(x << 1, l, mid), Build(x << 1 | 1, mid + 1, r);
}

inline void Insert(int x, int l, int r, int ql, int qr, pii v)
{
	if (l == ql && r == qr)
		return (void)(S[x].insert(v), mn[x].xx ++);
	int mid = l + r >> 1;
	if (qr <= mid)
		Insert(x << 1, l, mid, ql, qr, v);
	else if (ql > mid)
		Insert(x << 1 | 1, mid + 1, r, ql, qr, v);
	else
		Insert(x << 1, l, mid, ql, mid, v), Insert(x << 1 | 1, mid + 1, r, mid + 1, qr, v);
	Pushup(x);
}

inline void Add(int x, int y)
{
	int tx = x, ty = y;
	while (bel[tx] ^ bel[ty])
	{
		if (dep[bel[tx]] < dep[bel[ty]])
			swap(tx, ty);
		Insert(1, 2, n, dfn[bel[tx]], dfn[tx], mp(x, y));
		tx = par[bel[tx]];
	}
	if (dfn[tx] > dfn[ty])
		swap(tx, ty);
	if (tx ^ ty)
		Insert(1, 2, n, dfn[tx] + 1, dfn[ty], mp(x, y));
}

inline void Erase(int x, int l, int r, int ql, int qr, pii v)
{
	if (l == ql && r == qr)
		return (void)(S[x].erase(v), mn[x].xx --);
	int mid = l + r >> 1;
	if (qr <= mid)
		Erase(x << 1, l, mid, ql, qr, v);
	else if (ql > mid)
		Erase(x << 1 | 1, mid + 1, r, ql, qr, v);
	else
		Erase(x << 1, l, mid, ql, mid, v), Erase(x << 1 | 1, mid + 1, r, mid + 1, qr, v);
	Pushup(x);
}

inline void Del(int x, int y)
{
	int tx = x, ty = y;
	while (bel[tx] ^ bel[ty])
	{
		if (dep[bel[tx]] < dep[bel[ty]])
			swap(tx, ty);
		Erase(1, 2, n, dfn[bel[tx]], dfn[tx], mp(x, y));
		tx = par[bel[tx]];
	}
	if (dfn[tx] > dfn[ty])
		swap(tx, ty);
	if (tx ^ ty)
		Erase(1, 2, n, dfn[tx] + 1, dfn[ty], mp(x, y));
}

inline void GG()
{
	puts("NO");
	exit(0);
}

inline pii Query(int x, int l, int r, int p)
{
	if (S[x].size())
		return *S[x].begin();
	int mid = l + r >> 1;
	if (p <= mid)
		return Query(x << 1, l, mid, p);
	return Query(x << 1 | 1, mid + 1, r, p);
}
 
inline void Modify(int x, int l, int r, int p)
{
	if (l == r)
		return (void)(mn[x].xx = INF);
	int mid = l + r >> 1;
	if (p <= mid)
		Modify(x << 1, l, mid, p);
	else
		Modify(x << 1 | 1, mid + 1, r, p);
	Pushup(x);
}

int main()
{
#ifdef wxh010910
	freopen("data.in", "r", stdin);
#endif
	n = Read();
	for (int i = 1, x, y; i < n; i ++)
		x = Read(), y = Read(), adj[x].pb(y), adj[y].pb(x);
	Dfs(1), Dfs(1, 1), Build(1, 2, n);
	for (int i = 1, x, y; i < n; i ++)
		Add(Read(), Read());
	for (int i = 1; i < n; i ++)
	{
		if (mn[1].xx ^ 1)
			GG();
		int p = mn[1].yy;
		pii t = Query(1, 2, n, p);
		Del(t.xx, t.yy), Modify(1, 2, n, p);
	}
	return puts("YES"), 0;
}

Submission Info

Judge Result