Codeforces #668 Div1 B. Tree Tag

ここら辺もまだ難易度が低い。
https://codeforces.com/contest/1404/problem/B

問題

木を成すグラフで、2人交互にコマを動かすゲームを考える。
先手・後手の初期位置A,Bと、1手で移動できる距離DA,DBが与えられる。
各自自分の手番では、コマを現在位置からDA,DB以内の範囲で任意に移動できる。

先手が後手のコマと同じ位置に存在する瞬間が存在したら、先手の勝ちである。
後手が永遠に逃げ切れるなら、後手の勝ちである。
両者最適手を取るなら、勝者はどちらか。

解法

AからBの距離がDA以下なら、初手で先手が条件を満たす。
それ以外の場合、もし先手がBとの距離をDA以下に詰めた場合、後手の行動で距離を(DA+1)以上にできれば、後手は永遠に逃げ切れる。
よって、max(DB,直径)≦2*DAだと先手の勝ちとなる。

int T;
int N,A,B,DA,DB;
vector<int> E[101010];

int D[101010];

pair<int,int> farthest(int cur,int pre,int d,vector<int>& D) {
	D[cur]=d;
	pair<int,int> r={d,cur};
	FORR(e,E[cur]) if(e!=pre) r=max(r, farthest(e,cur,d+1,D));
	return r;
}

pair<int,vector<int>> diameter() { // diameter,center
	vector<int> D[2];
	D[0].resize(N);
	D[1].resize(N);
	auto v1=farthest(0,0,0,D[0]);
	auto v2=farthest(v1.second,v1.second,0,D[0]);
	farthest(v2.second,v2.second,0,D[1]);
	pair<int,vector<int>> R;
	R.first = v2.first;
	//重心を取る場合
	for(int i=N-1;i>=0;i--) if(D[0][i]+D[1][i]==R.first && abs(D[0][i]-D[1][i])<=1) R.second.push_back(i);
	//両端を取る場合
	R.second.push_back(v1.second);
	R.second.push_back(v2.second);

	return R;
}

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

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>A>>B>>DA>>DB;
		A--,B--;
		FOR(i,N) {
			E[i].clear();
			D[i]=1<<20;
		}
		FOR(i,N-1) {
			cin>>x>>y;
			E[x-1].push_back(y-1);
			E[y-1].push_back(x-1);
		}
		if(DB<=DA*2) {
			cout<<"Alice"<<endl;
			continue;
		}
		dfs(A,A,0);
		if(D[B]<=DA) {
			cout<<"Alice"<<endl;
			continue;
		}
		auto R=diameter();
		if(R.first<=2*DA) {
			cout<<"Alice"<<endl;
		}
		else {
			cout<<"Bob"<<endl;
		}
		
	}
}

まとめ

直径ライブラリがあると簡単。