AtCoder ABC #148 : F - Playing Tag on Tree

割と典型。
https://atcoder.jp/contests/abc148/tasks/abc148_f

問題

木を成すグラフで2つの駒がある。
2人で自分の駒を1ターン毎に必ず隣接頂点のどこかに動かすとする。
駒が重なったらゲームが終了となる。
先手は駒が重なるターンを遅らせようとし、後手は早めようとする場合、最大で後手が何回移動したところでゲームが終了となるか。

解法

各頂点、両駒の始点からの距離を求めよう。
先手は、先手の方が速く到達できる頂点のうち、後手から最も遠い点に逃げる。
なお、先手は最遠点に到達しても、自身のターンで必ず移動しないといけないことを踏まえると、実際に両者が合流するのは1つ手前の点になる。(初期状態の両者の距離が奇数の場合と偶数の場合で考えてみるとよい)

int N,A,B;
vector<int> E[101010];
int D[101010][2];

void dfs(int cur,int pre,int d,int id) {
	D[cur][id]=d;
	FORR(e,E[cur]) if(e!=pre) dfs(e,cur,d+1,id);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>A>>B;
	A--,B--;
	FOR(i,N-1) {
		cin>>x>>y;
		E[x-1].push_back(y-1);
		E[y-1].push_back(x-1);
	}
	dfs(A,A,0,0);
	dfs(B,B,0,1);
	
	int ma=0;
	FOR(i,N) if(D[i][0]<D[i][1]) ma=max(ma,D[i][1]-1);
	cout<<ma<<endl;
	
}

まとめ

これも今までなら500ptになってそう。