Submission #7942593

---

Source Code Expand

#include<bits/stdc++.h>
typedef long long ll;
ll gi(){
	ll x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))f^=ch=='-',ch=getchar();
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return f?x:-x;
}
int ea[200010],eb[200010];
bool ya[200010];
struct tree{
	int fir[200010],dis[400010],nxt[400010],id,fa[200010],dep[200010];
	void link(int a,int b){nxt[++id]=fir[a],fir[a]=id,dis[id]=b;}
	void dfs(int x,int*Bd=0){
		if(Bd&&dep[x]>=Bd[x]){return;}
		for(int i=fir[x];i;i=nxt[i]){
			if(fa[x]==dis[i])continue;
			fa[dis[i]]=x;
			dep[dis[i]]=dep[x]+1;
			dfs(dis[i],Bd);
		}
	}
}A,B;
int main(){
#ifdef XZZSB
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
#endif
	int n=gi(),sa=gi(),sb=gi(),a,b;
	for(int i=1;i<n;++i)ea[i]=gi(),eb[i]=gi();
	for(int i=1;i<n;++i)a=gi(),b=gi(),B.link(a,b),B.link(b,a);
	B.dfs(sb);
	for(int i=1;i<n;++i)
		if(B.fa[ea[i]]==eb[i]||
		   B.fa[eb[i]]==ea[i]||
		   B.fa[B.fa[ea[i]]]==eb[i]||
		   B.fa[B.fa[eb[i]]]==ea[i]||
		   B.fa[ea[i]]==B.fa[eb[i]])
			A.link(ea[i],eb[i]),A.link(eb[i],ea[i]);
		else ya[ea[i]]=ya[eb[i]]=1;
	memset(A.dep,-1,sizeof A.dep);A.dep[sa]=0,A.dfs(sa,B.dep);
	for(int i=1;i<=n;++i)if(~A.dep[i]&&ya[i]&&A.dep[i]<B.dep[i])return puts("-1"),0;
	int ans=0;
	for(int i=1;i<=n;++i)if(~A.dep[i])ans=std::max(ans,B.dep[i]);
	printf("%d\n",ans*2);
	return 0;
}

Submission Info

Judge Result