CF1405D Tree Tag（树的直径/博弈）

#include <bits/stdc++.h>
#define N 300005
using namespace std;
int n, a, b, da, db;
int head[N], ver[2 * N], Next[2 * N], tot = 0;
int p1, p2, mxd = 0;
int dep[N];
int linklen = 0;
int disab;
void add(int x, int y) {
	ver[++tot] = y, Next[tot] = head[x], head[x] = tot;
}
void dfs1(int x, int pre, int d) {
	dep[x] = d;
	if(x == b) {
		disab = d - 1;
	}
	if(d > mxd) {
		mxd = d;
		p1 = x;
	}
	for(int i = head[x]; i; i = Next[i]) {
		int y = ver[i];
		if(y == pre) continue;
		dfs1(y, x, d + 1);
	}
}
void dfs2(int x, int pre, int d) {
	if(d > linklen) {
		linklen= d;
		p2 = x;

	}
	for(int i = head[x]; i; i = Next[i]) {
		int y = ver[i];
		if(y == pre) continue;
		dfs2(y, x, d + 1);
	}
}
void solve() {
	cin >> n >> a >> b >> da >> db;
	tot = 0;
	for(int i = 1; i <= n; i++) {
		head[i] = 0;
	}
	mxd = linklen = 0;
	for(int i = 2; i <= n; i++) {
		int u, v;
		cin >> u >> v;
		add(u, v);
		add(v, u);
	}
	dfs1(a, 0, 1);
	dfs2(p1, 0, 1);
	linklen--;//直径上边的数目
	if(2 * da >= linklen) {//Alice先跳回中心然后就可以直接跳到任何地方
		puts("Alice");
	} else if(disab <= da) {//Alice一步就可以到bob
		puts("Alice");
	} else if(db <= 2 * da) {//Alice可以把Bob逼近角落而Bob无法挣脱
		puts("Alice");
	} else {
		puts("Bob");
	}

}
int main() {
	int T = 1;
	cin >> T;
	while(T--) {
		solve();
	}
	return 0;
}

原文地址：http://www.cnblogs.com/lipoicyclic/p/16852489.html