Submission #1442694

---

Source Code Expand

// This amazing code is by Eric Sunli Chen.
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <vector>
using namespace std;
template<typename T> void get_int(T &x)
{
	char t=getchar();
	bool neg=false;
	x=0;
	for(; (t>'9'||t<'0')&&t!='-'; t=getchar());
	if(t=='-')neg=true,t=getchar();
	for(; t<='9'&&t>='0'; t=getchar())x=x*10+t-'0';
	if(neg)x=-x;
}
template<typename T> void print_int(T x)
{
	if(x<0)putchar('-'),x=-x;
	short a[20]= {},sz=0;
	while(x>0)a[sz++]=x%10,x/=10;
	if(sz==0)putchar('0');
	for(int i=sz-1; i>=0; i--)putchar('0'+a[i]);
}
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define get1(a) get_int(a)
#define get2(a,b) get1(a),get1(b)
#define get3(a,b,c) get1(a),get2(b,c)
#define printendl(a) print_int(a),puts("")
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int,int> pii;
const int inf=0x3f3f3f3f;
const LL Linf=1ll<<61;
const double pi=acos(-1.0);

int n;
struct tree1
{
	vector<int> g[200111];
	int fa[200111][20],dep[200111];
	void addedge(int u,int v)
	{
		g[u].pb(v);
		g[v].pb(u);
	}
	void dfs(int x,int f=0)
	{
		fa[x][0]=f;
		for(int i=0;i<(int)g[x].size();i++)
			if(g[x][i]!=f)
			{
				dep[g[x][i]]=dep[x]+1;
				dfs(g[x][i],x);
			}
	}
	void prework(int s)
	{
		dfs(s);
		for(int i=1;i<20;i++)for(int j=1;j<=n;j++)fa[j][i]=fa[fa[j][i-1]][i-1];
	}
	int getlca(int x,int y)
	{
		if(dep[x]<dep[y])swap(x,y);
		for(int i=0;i<20;i++)if((dep[x]-dep[y]>>i)&1)x=fa[x][i];
		if(x==y)return x;
		for(int i=19;i>=0;i--)if(fa[x][i]!=fa[y][i])
		{
			x=fa[x][i];
			y=fa[y][i];
		}
		return fa[x][0];
	}
	int dist(int x,int y)
	{
		return dep[x]+dep[y]-dep[getlca(x,y)]*2;
	}
}m1;
int sx,sy,ex[200111],ey[200111],ans;
bool kill[200111];
vector<int> g[200111];
int dep[200111];
void dfs(int x,int f=0)
{
//	printf("dfs %d %d d2= %d\n",x,f,m1.dep[x]);
	if(dep[x]>=m1.dep[x])return;
	ans=max(ans,m1.dep[x]*2);
	if(kill[x])
	{
		puts("-1");
		exit(0);
	}
	for(int i=0;i<(int)g[x].size();i++)
		if(g[x][i]!=f)
		{
			dep[g[x][i]]=dep[x]+1;
			dfs(g[x][i],x);
		}
}
int main()
{
	get3(n,sx,sy);
	for(int i=1,u,v;i<n;i++)get2(ex[i],ey[i]);
	for(int i=1,u,v;i<n;i++)
	{
		get2(u,v);
		m1.addedge(u,v);
	}
	m1.prework(sy);
	for(int i=1;i<n;i++)
	{
		if(m1.dist(ex[i],ey[i])>=3)kill[ex[i]]=kill[ey[i]]=1;
		else
		{
			g[ex[i]].pb(ey[i]);
			g[ey[i]].pb(ex[i]);
		}
	}
	dfs(sx);
	printendl(ans);
	return 0;
}

Submission Info

Judge Result