Submission #1982272

---

Source Code Expand

#include<cstdio>
#include<vector>
#define pb push_back
const int MaxN=100010,mod=10000019;
int N,a[MaxN],b[MaxN],c[MaxN],d[MaxN];
struct item{
	int ty,u,v,x;item*next;
	bool eq(int a,int b){return u==a&&v==b||u==b&&v==a;}
	int h(){return(1ll*(u<v?u:v)*N+(u>v?u:v))%mod;}
}E1[MaxN],E2[MaxN],*fir[mod];
int op[MaxN],Q[MaxN],*head=Q,*tail=Q;
void mov(item*e,int x,int y){
	item*it=fir[e->h()];
	if(it==e)fir[e->h()]=e->next;
	else if(it){
		while(it->next!=e)it=it->next;
		it->next=e->next;
	}
	e->u=x;e->v=y;
	e->next=fir[e->h()];
	fir[e->h()]=e;
}
struct edge{int id,to;edge*rev,*next;};
struct tree{
	edge E[MaxN*2],*ne=E,*first[MaxN];
	int deg[MaxN];
	bool del[MaxN];
	void link(int id,int u,int v){
		*ne=(edge){id,v,ne+1,first[u]};first[u]=ne++;
		*ne=(edge){id,u,ne-1,first[v]};first[v]=ne++;
		deg[u]++;deg[v]++;
	}
	void rm(int e,int u,int v){
		del[e]=1;
		deg[u]--;deg[v]--;
	}
	void mig(int u,int v,bool ty){ // u->v
		for(edge*e=first[u],*ex;e;e=ex){
			ex=e->next;
			if(del[e->id])continue;
			e->rev->to=v;
			int&x=(ty?c:a)[e->id],&y=(ty?d:b)[e->id];
			x==u?x=v:y=v;
			if(ty){
				mov(E2+e->id,x,y);
				if(!op[e->id])
					for(item*it=fir[E2[e->id].h()];it;it=it->next)
						if(!it->ty&&it->eq(x,y))op[*tail++=e->id]=it->x;
			}
			else{
				mov(E1+e->id,x,y);
				for(item*it=fir[E1[e->id].h()];it;it=it->next)
					if(it->ty&&!op[it->x]&&it->eq(x,y))op[*tail++=it->x]=e->id;
			}
			e->next=first[v];
			first[v]=e;
		}
		deg[v]+=deg[u];
		deg[u]=0;
	}
}T1,T2;
bool get_dup(int&e1,int&e2){
	if(head==tail)return 0;
	e1=op[e2=*head++];
	return 1;
}
bool solve(){
	for(int i=1;i<N;i++){
		E1[i]=(item){0,a[i],b[i],i,0};
		E1[i].next=fir[E1[i].h()];
		fir[E1[i].h()]=E1+i;
	}
	for(int i=1;i<N;i++){
		E2[i]=(item){1,c[i],d[i],i,0};
		for(item*it=E2[i].next=fir[E2[i].h()];it;it=it->next)
			if(it->eq(c[i],d[i])&&!op[i])op[*tail++=i]=it->x;
		fir[E2[i].h()]=E2+i;
	}
	for(int t=N;--t;){
		int e1,e2,u,v;
		if(!get_dup(e1,e2))return 0;
		u=a[e1],v=b[e1];
		T1.rm(e1,u,v);
		T2.rm(e2,u,v);
		if(T1.deg[u]+T2.deg[u]>T1.deg[v]+T2.deg[v]){
			int w=u;u=v;v=w;
		}
		T1.mig(u,v,0);
		T2.mig(u,v,1);
	}
	return 1;
}
int main(){
	scanf("%d",&N);
	for(int i=1;i<N;i++)scanf("%d%d",a+i,b+i),T1.link(i,a[i],b[i]);
	for(int i=1;i<N;i++)scanf("%d%d",c+i,d+i),T2.link(i,c[i],d[i]);
	puts(solve()?"YES":"NO");
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:94:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
                ^
./Main.cpp:95:64: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<N;i++)scanf("%d%d",a+i,b+i),T1.link(i,a[i],b[i]);
                                                                ^
./Main.cpp:96:64: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<N;i++)scanf("%d%d",c+i,d+i),T2.link(i,c[i],d[i]);
                                                                ^

Judge Result