Submission #1732059

---

Source Code Expand

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;
 
int par[111111];
set<ii> R,B;
vi adjr[111111];
vi adjb[111111];

int rt(int u)
{
	if(par[u]<0) return u;
	else return (par[u]=rt(par[u]));
}

queue<ii> q;
int res;

void merge(int u, int v)
{
	u=rt(u); v=rt(v);
	if(u==v) return ;
	res++;
	if(par[u]>par[v]) swap(u,v);
	//v merges to u
	par[u]+=par[v]; par[v]=u;
	for(int i=0;i<adjr[v].size();i++)
	{
		int val=adjr[v][i]; val=rt(val);
		if(val==u) continue;
		adjr[u].pb(val);
		R.insert(mp(u,val));
		if(B.find(mp(u,val))!=B.end()||B.find(mp(val,u))!=B.end()) q.push(mp(u,val));
	}
	for(int i=0;i<adjb[v].size();i++)
	{
		int val=adjb[v][i]; val=rt(val);
		if(val==u) continue;
		adjb[u].pb(val);
		B.insert(mp(u,val));
		if(R.find(mp(u,val))!=R.end()||R.find(mp(val,u))!=R.end()) q.push(mp(u,val));
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	memset(par,-1,sizeof(par));
	int n; cin>>n;
	for(int i=0;i<n-1;i++)
	{
		int u,v; cin>>u>>v;
		u--; v--;
		R.insert(mp(u,v));
		adjr[u].pb(v); adjr[v].pb(u);
	}
	for(int i=0;i<n-1;i++)
	{
		int u,v; cin>>u>>v;
		u--; v--;
		B.insert(mp(u,v));
		adjb[u].pb(v); adjb[v].pb(u);
		if(R.find(mp(u,v))!=R.end()||R.find(mp(v,u))!=R.end())
		{
			q.push(mp(u,v));
		}
	}
	res=0;
	while(!q.empty())
	{
		int u=q.front().fi; int v=q.front().se; q.pop();
		merge(u,v);
	}
	cout<<(res==n-1?"YES":"NO")<<'\n';
}

Submission Info

Judge Result