Submission #1691398

---

Source Code Expand

#include<cstdio>
#include<algorithm>
using namespace std;
inline int read()
{
	int x;char c;
	while((c=getchar())<'0'||c>'9');
	for(x=c-'0';(c=getchar())>='0'&&c<='9';)x=x*10+c-'0';
	return x;
}
#define MN 200000
#define K 18
struct edge{int nx,t;}e[MN*4+5];
int A[MN+5],B[MN+5],en,fa[K][MN+5],d[MN+5],ans;
inline void ins(int*h,int x,int y)
{
	e[++en]=(edge){h[x],y};h[x]=en;
	e[++en]=(edge){h[y],x};h[y]=en;
}
void pre(int x)
{
	for(int i=B[x];i;i=e[i].nx)if(e[i].t!=fa[0][x])
		d[e[i].t]=d[fa[0][e[i].t]=x]+1,pre(e[i].t);
}
int lca(int x,int y)
{
	if(d[x]<d[y])swap(x,y); 
	int k=d[x]-d[y],i;
	for(i=0;k;k>>=1,++i)if(k&1)x=fa[i][x];
	if(x==y)return x;
	for(i=K;i--;)if(fa[i][x]!=fa[i][y])x=fa[i][x],y=fa[i][y];
	return fa[0][x];
}
void solve(int x,int y,int f,int p)
{
	if(x==y)return;
	ans=max(ans,d[x]+d[y]-d[lca(x,y)]*2+p);
	for(int i=A[x];i;i=e[i].nx)if(e[i].t!=f&&e[i].t!=y)
	{
		if(d[x]+d[e[i].t]-d[lca(x,e[i].t)]*2>2)ans=2e9;
		if(lca(e[i].t,y)==y)
		{
			int t=e[i].t,k=d[t]-d[y]-1,j;
			for(j=0;k;k>>=1,++j)if(k&1)t=fa[j][t];
			solve(e[i].t,t,x,p+1);
		}
		else solve(e[i].t,fa[0][y],x,p+1);
	}
}
int main()
{
	int n,x,y,i,j;
	n=read();x=read();y=read();
	for(i=1;i<n;++i)ins(A,read(),read());
	for(i=1;i<n;++i)ins(B,read(),read());
	pre(1);
	for(i=1;i<K;++i)for(j=1;j<=n;++j)fa[i][j]=fa[i-1][fa[i-1][j]];
	solve(x,y,0,0);
	printf("%d",ans>1e9?-1:ans<<1);
}

Submission Info

Judge Result