Submission #1589718

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<cstring>
#define repst(p) for(int i=begin[p],q;i;i=next[i])if((q=to[i])!=h)
#define rept(p,t) for(int i=t.begin[p],q;i;i=t.next[i])if((q=t.to[i])!=h)
template<typename T>inline void check_max(T a,T &b){if(a>b)b=a;}
template<typename T>inline void read(T &x)
{
	char c=x=0;
	for(c=getchar();!isdigit(c);c=getchar());
	for(;isdigit(c);c=getchar())x=(x<<3)+(x<<1)+(c^48);
}
namespace wrong
{
	const int N=201000,M=N*2;
	struct tool
	{
		int begin[N],next[M],to[M];
		int fa[N][20],dep[N];
		int e;
		void add(int x,int y,bool k=1)
		{
			to[++e]=y;
			next[e]=begin[x];
			begin[x]=e;
			if(k)add(y,x,0);
		}
		void predfs(int p=1,int h=0)
		{
			dep[p]=dep[h]+1;
			for(int k=1;k<=18;k++)
				fa[p][k]=fa[fa[p][k-1]][k-1];
			repst(p)
			{
				fa[q][0]=p;
				predfs(q,p);
			}
		}
		int get_lca(int u,int v)
		{
			if(dep[u]<dep[v])std::swap(u,v);
			for(int k=18;k>=0;k--)
				while(dep[fa[u][k]]>=dep[v])u=fa[u][k];
			for(int k=18;k>=0;k--)
				while(fa[u][k]!=fa[v][k])
					u=fa[u][k],v=fa[v][k];
			return u==v?u:fa[u][0];
		}
		int dis(int u,int v){return dep[u]+dep[v]-2*dep[get_lca(u,v)];}
		bool check(int u,int v)
		{
			if(dep[u]<dep[v])std::swap(u,v);
			if(fa[u][0]==v || fa[u][1]==v)return 0;
			if(fa[u][0]==fa[v][0])return 0;
			return 1;
		}
		int go(int p,int q)
		{
			if(dep[p]>=dep[q])return fa[p][0];
			for(int k=18;k>=0;k--)
				while(dep[fa[q][k]]>dep[p])q=fa[q][k];
			if(fa[q][0]==p)return q;
			return fa[p][0];
		}
	}s,t;
	int f[N],g[N];
	bool isit[N];
	int n,X,Y;
	void initialize()
	{
		read(n),read(X),read(Y);
		for(int i=1,u,v;i<n;i++)
			read(u),read(v),s.add(u,v);
		for(int i=1,u,v;i<n;i++)
			read(u),read(v),t.add(u,v);
		t.predfs();
		f[X]=Y,g[X]=0;
	}
	void dfs(int p=X,int h=0)
	{

		if(p==f[p])return;
		rept(p,s)
		{
			if(t.check(p,q))isit[p]=isit[q]=1;
			if(q==f[p])continue;
			f[q]=t.go(f[p],q);
			g[q]=g[p]+1;
			dfs(q,p);
		}
	}
	int getans()
	{
		int ret=0;
		for(int i=1;i<=n;i++)
		{
			if(!f[i])continue;
			if(f[i]!=i && isit[i])return -1;
//			printf("%d %d %d\n",i,f[i],g[i]);

			check_max(g[i]+t.dis(i,f[i]),ret);
		}
		return ret*2;
	}
	void solve()
	{
		initialize();
		dfs();
		printf("%d\n",getans());
	}
}
int main()
{
//	freopen("in","r",stdin);
	wrong::solve();
	return 0;
}

Submission Info

Judge Result