Submission #1753064

---

Source Code Expand

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
#define ll long long
#define RG register 
#define REP(i,a,b) for(RG int i=(a),_end_=(b);i<=_end_;i++)
#define DREP(i,a,b) for(int i=(a),_end_=(b);i>=_end_;i--)
#define EREP(i,a) for(int i=start[(a)];i;i=e[i].next)
inline int read()
{
	RG int sum=0,p=1;RG char ch=getchar();
	while(!(('0'<=ch && ch<='9') || ch=='-'))ch=getchar();
	if(ch=='-')p=-1,ch=getchar();
	while('0'<=ch && ch<='9')sum=sum*10+ch-48,ch=getchar();
	return sum*p;
}

const int maxn=2e5+20;

struct edge {
	int u,v;
};
edge ed[maxn];

struct node {
	int v,next;
};
node e[maxn*2];
int cnt,start[maxn];
inline void addedge(int u,int v)
{
	e[++cnt]=(node){v,start[u]};
	start[u]=cnt;
}

int n;

inline void init()
{
	n=read();
	REP(i,1,n-1)
	{
		int u=read(),v=read();
		ed[i]=(edge){u,v};
	}
	cnt=0;REP(i,1,n)start[i]=0;
	REP(i,1,n-1)
	{
		int u=read(),v=read();
		addedge(u,v);
		addedge(v,u);
	}
}

vector<int>g[maxn];
int fa[maxn];
inline int fin(int x){return x==fa[x]?x:fa[x]=fin(fa[x]);}

inline bool check(int x,int y)
{
	REP(j,0,g[x].size()-1)
	{
		RG int u=g[x][j];
		EREP(i,u)
		{
			if(fin(e[i].v)==y)return true;
		}
	}
	return false;
}

int lst[maxn],nxt[maxn];

inline void doing()
{
	REP(i,1,n)fa[i]=i,g[i].clear(),g[i].push_back(i);
	REP(i,1,n-1)lst[i]=i-1,nxt[i]=i+1;nxt[n-1]=0;
	nxt[0]=1;
	int flag=0;
	do{
		flag=0;
		for(RG int i=nxt[0];i;i=nxt[i])
		{
			RG int u=fin(ed[i].u),v=fin(ed[i].v);
			if(g[u].size()<g[v].size())swap(u,v);
			if(!check(v,u))continue;
			flag=1;
			fa[v]=u;REP(j,0,g[v].size()-1)g[u].push_back(g[v][j]);
			nxt[lst[i]]=nxt[i];
			lst[nxt[i]]=lst[i];
		}
	}while(flag);
	int s=0;
	REP(i,1,n)if(fin(i)==i)s++;
	if(s==1)printf("YES\n");
	else printf("NO\n");
}

int main()
{
		init();
		doing();
	return 0;
}

Submission Info

Judge Result