Submission #3452439

---

Source Code Expand

#include<algorithm>
#include<cstring>
#include<cstdio>
#include<cctype>
#define rep(i,x,y) for(int i=x; i<=y; ++i)

using namespace std;
const int N=200005;
int n,vis[N],ans;
struct edge{int v,n;};

int getint()
{
	char ch;
	while(!isdigit(ch=getchar()));
	int x=ch-48;
	while(isdigit(ch=getchar())) x=x*10+ch-48;
	return x;
}

struct tree
{
	int h[N],cnt,dep[N],fa[N],root;
	edge e[N<<1];

	void addedge(int u,int v)
	{
		e[cnt]=(edge){v,h[u]},h[u]=cnt++;
		e[cnt]=(edge){u,h[v]},h[v]=cnt++;
	}
	
	void dfs(int x,int f,int d)
	{
		dep[x]=d,fa[x]=f;
		for(int i=h[x]; i!=-1; i=e[i].n)
			if(e[i].v!=f) dfs(e[i].v,x,d+1);
	}

	void build()
	{
		memset(h,-1,sizeof(h));
		rep(i,1,n-1) addedge(getint(),getint());
		dfs(root,0,0);
	}

	bool query(int x,int y)
	{
		int rt=0;
		while(x!=y)
		{
			if(++rt,dep[x]>dep[y]) x=fa[x];
			else y=fa[y];
			if(rt>2) return 1;
		}
		return 0;
	}
} t1,t2;

void dfs(int x,int fa)
{
	if(t1.dep[x]>=t2.dep[x]) return;
	vis[x]=1;
	for(int i=t1.h[x]; i!=-1; i=t1.e[i].n)
		if(t1.e[i].v!=fa) dfs(t1.e[i].v,x);
}

int main()
{
	n=getint(),t1.root=getint(),t2.root=getint();
	t1.build(),t2.build(),dfs(t1.root,0);
	rep(i,1,n) if(vis[i])
	{
		ans=max(ans,t2.dep[i]);
		for(int j=t1.h[i]; j!=-1; j=t1.e[j].n)
			if(t2.query(i,t1.e[j].v))
				return puts("-1"),0;
	}
	printf("%d\n",ans*2);
	return 0;
}

Submission Info

Judge Result