Submission #1692549

---

Source Code Expand

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;

inline int read(){
	int x;char c;
	while((c=getchar())<'0'||c>'9');
	x=c-48;
	while((c=getchar())>='0'&&c<='9')x=x*10+c-48;
	return x;
}

const int maxn=2e5+10;
int n,a,b,uu[maxn],vv[maxn],dep[maxn],fa[20][maxn],dist[maxn],ans;
int ecnt,ebeg[maxn],enxt[maxn<<1],eto[maxn<<1];
int eecnt,eebeg[maxn],eenxt[maxn<<1],eeto[maxn<<1];
bool safe[maxn];

inline void ae(int u,int v){
	++ecnt;
	enxt[ecnt]=ebeg[u];
	ebeg[u]=ecnt;
	eto[ecnt]=v;
}
inline void aee(int u,int v){
	++eecnt;
	eenxt[eecnt]=eebeg[u];
	eebeg[u]=eecnt;
	eeto[eecnt]=v;
}
inline void chkmax(int&a,int b){
	if(a<b)a=b;
}
void dfs(int pos){
	for(int i=ebeg[pos],v;i;i=enxt[i])
		if((v=eto[i])!=fa[0][pos]){
			fa[0][v]=pos;
			dep[v]=dep[pos]+1;
			dfs(v);
		}
}
int lca(int u,int v){
	if(dep[u]<dep[v])u^=v,v^=u,u^=v;
	for(int i=19;~i;--i)
		if(dep[fa[i][u]]>dep[v])
			u=fa[i][u];
	if(dep[u]>dep[v])
		u=fa[0][u];
	for(int i=19;~i;--i)
		if(fa[i][u]!=fa[i][v])
			u=fa[i][u],v=fa[i][v];
	if(u!=v)
		u=fa[0][u],v=fa[0][v];
	return u;
}
void dfss(int pos,int last){
	chkmax(ans,dep[pos]);
	if(dist[pos]>=dep[pos])
		return;
	if(safe[pos]){
		puts("-1");
		exit(0);
	}
	for(int i=eebeg[pos];i;i=eenxt[i])
		if(eeto[i]!=last){
			dist[eeto[i]]=dist[pos]+1;
			dfss(eeto[i],pos);
		}
}

int main(){
	n=read();a=read();b=read();
	for(int i=1;i<n;++i)
		uu[i]=read(),vv[i]=read();
	for(int i=1,u,v;i<n;++i){
		u=read();v=read();
		ae(u,v);
		ae(v,u);
	}
	dfs(b);
	for(int i=1;i<20;++i)
		for(int j=1;j<=n;++j)
			fa[i][j]=fa[i-1][fa[i-1][j]];
	for(int i=1,u,v;i<n;++i){
		u=uu[i];v=vv[i];
		aee(u,v);aee(v,u);
		if(dep[u]+dep[v]-dep[lca(u,v)]*2>=3)
			safe[u]=safe[v]=true;
	}
	dfss(a,0);
	printf("%d\n",ans*2);
	return 0;
}

Submission Info

Judge Result