Submission #2230875

---

Source Code Expand

#include<iostream>
#include<cstdio>
#define MN 100000
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,head[MN+5],cnt=0,a[MN+5],b[MN+5],H[MN*4+5],dep[MN+5];
int dfn[MN+5],top[MN+5],size[MN+5],mx[MN+5],Fa[MN+5],dn=0,vis[MN+5];
struct edge{int to,next;}e[15000005];
struct data{pair<int,int> mn,mn2;
	data operator + (const data&b)
	{
		data c;
		if(mn.first==b.mn.first) c.mn=mn,c.mn2=min(mn2,b.mn2);
		else if(mn<b.mn) c.mn=mn,c.mn2=min(mn2,b.mn);
		else c.mn=b.mn,c.mn2=min(mn,b.mn2);
		return c;
	} 
};
struct Tree{int l,r,val;data x;}T[MN*4+5];
inline void ins(int*h,int f,int t){e[++cnt]=(edge){t,h[f]};h[f]=cnt;}
void Pre(int x,int fa)
{
	size[x]=1;mx[x]=0;Fa[x]=fa;
	for(int i=head[x];i;i=e[i].next)
		if(e[i].to!=fa)
		{
			dep[e[i].to]=dep[x]+1;
			Pre(e[i].to,x);
			size[x]+=size[e[i].to];
			if(size[e[i].to]>size[mx[x]]) mx[x]=e[i].to;
		}
}
void Dfs(int x,int tp)
{
	top[x]=tp;dfn[x]=++dn;
	if(mx[x]) Dfs(mx[x],tp);
	for(int i=head[x];i;i=e[i].next)
		if(e[i].to!=Fa[x]&&e[i].to!=mx[x])
			Dfs(e[i].to,e[i].to);
}
void Build(int x,int l,int r)
{
	if((T[x].l=l)==(T[x].r=r)){T[x].x=(data){make_pair(0,l),make_pair(1e9,0)};return;}
	int mid=l+r>>1;	
	Build(x<<1,l,mid),Build(x<<1|1,mid+1,r);
	T[x].x=T[x<<1].x+T[x<<1|1].x;
}
inline void Mark(int x,int v){T[x].val+=v;T[x].x.mn.first+=v;T[x].x.mn2.first+=v;}
inline void pushdown(int x){Mark(x<<1,T[x].val),Mark(x<<1|1,T[x].val),T[x].val=0;}
void Modify(int x,int l,int r,int v,int fr)
{
	if(T[x].l==l&&T[x].r==r)
	{
		if(v>0) ins(H,x,fr);
		return Mark(x,v);;
	}
	if(T[x].val) pushdown(x);
	int mid=T[x].l+T[x].r>>1;
	if(r<=mid) Modify(x<<1,l,r,v,fr);
	else if(l>mid) Modify(x<<1|1,l,r,v,fr);
	else Modify(x<<1,l,mid,v,fr),Modify(x<<1|1,mid+1,r,v,fr);
	T[x].x=T[x<<1].x+T[x<<1|1].x;
}
int Get(int x,int k)
{
	while(H[x]&&vis[e[H[x]].to]) H[x]=e[H[x]].next;
	if(H[x]) return e[H[x]].to;
	if(T[x].l==T[x].r) return printf("what a fuck?\n");
	int mid=T[x].l+T[x].r>>1;
	if(T[x].val) pushdown(x);
	return Get(x<<1|(k>mid),k);
}
void Solve(int x,int y,int v,int i)
{
	for(;top[x]!=top[y];x=Fa[top[x]])
	{
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		Modify(1,dfn[top[x]],dfn[x],v,i);
	}
	if(dfn[x]>dfn[y]) swap(x,y);
	if(dfn[x]<dfn[y]) Modify(1,dfn[x]+1,dfn[y],v,i);	
}
int main()
{
	n=read();
	for(int i=1;i<n;++i)
	{
		int x=read(),y=read();
		ins(head,x,y);ins(head,y,x);
	}
	Pre(1,0);Dfs(1,1);Build(1,1,n);
	for(int i=1;i<n;++i)
	{
		a[i]=read();b[i]=read();
		Solve(a[i],b[i],1,i);
	}
	for(int i=1;i<n;++i)
	{
		int fr=T[1].x.mn.first==1?T[1].x.mn.second:(T[1].x.mn2.first==1?T[1].x.mn2.second:0);
		if(!fr) return 0*puts("NO");
		int res=Get(1,fr);vis[res]=1;
		Solve(a[res],b[res],-1,i);
	}
	puts("YES");
	return 0;
}

Submission Info

Judge Result