AGC 005 E Sugigma: The Showdown

問題: E - Sugigma: The Showdown

まず、しぐま君 (追いかけられる方のプレイヤー) の必勝条件について考える。
すぎむ君 (追いかける方のプレイヤー) の木において、距離が 3 以上離れた頂点を行き来できるような頂点に先に到達し、直後のターンに負けないことと同値となっている。
適当な根としたすぎむ君の木について考えると、距離が 3 以上離れた頂点であるかの判定が簡単にできる。(この判定方法を思いつくのは少しむずかしいかも)

必勝となる頂点を確定させたあとは、すぎむ君、しぐま君の順で、交互に BFS をしながらお互いの動ける範囲を計算すればよい。(すぎむ君、しぐま君の順で計算するのは本質では無いが、少しだけ見通しがよくなる)

#define N 200100
vector<int> g[N], g2[N];
int n, x, y, a[N], b[N], c[N], d[N];
int d2[N], w[N], used[N], p[N];

int dfs2(int u){
	for(auto v: g2[u]){
		if(d2[v]<0){
			d2[v] = d2[u]+1;
			dfs2(v);
			p[v] = u;
		}
	}
}

int main(){
	cin>>n>>x>>y; x--; y--;
	rep(i, n-1) cin>>a[i]>>b[i];
	rep(i, n-1) cin>>c[i]>>d[i];
	rep(i, n-1){
		a[i]--; b[i]--;
		g[a[i]].pb(b[i]);
		g[b[i]].pb(a[i]);
	}
	rep(i, n-1){
		c[i]--; d[i]--;
		g2[c[i]].pb(d[i]);
		g2[d[i]].pb(c[i]);
	}
	mset(d2, -1);
	d2[y] = 0;
	dfs2(y);
	p[y] = -1;
	rep(i, n-1){
		int t = d2[a[i]]-d2[b[i]];
		if(abs(t)>2){
			w[a[i]] = 1;
			w[b[i]] = 1;
			continue;
		}
		int a2 = a[i], b2 = b[i];
		if(t==0){
			a2 = p[a2];
			b2 = p[b2];
		}
		while(t>0){
			a2 = p[a2];
			t--;
		}
		while(t<0){
			b2 = p[b2];
			t++;
		}
		if(a2!=b2){
			w[a[i]] = 1;
			w[b[i]] = 1;
		}
	}
	queue<int> q, q2;
	q.push(x); q2.push(y);
	w[y] = -1;
	if(w[x]==1){
		cout<<-1<<endl;
		return 0;
	}
	w[x] = 2;
	int cnt = 1;
	for(int i = 2; ; i+=2){
		queue<int> q3, q4;
		while(!q2.empty()){
			int u = q2.front(); q2.pop();
			for(auto v: g2[u]){
				if(w[v]<0) continue;
				if(w[v]==2) cnt--;
				w[v] = -1;
				q4.push(v);
			}
		}
		while(!q.empty()){
			int u = q.front(); q.pop();
			for(auto v: g[u]){
				if(w[v]<0||w[v]==2) continue;
				if(w[v]==1){
					cout<<-1<<endl;
					return 0;
				}
				w[v] = 2;
				cnt++;
				q3.push(v);
			}
		}
		if(cnt==0){
			cout<<i<<endl;
			break;
		}
		q.swap(q3);
		q2.swap(q4);
	}
	return 0;
}