题目地址：http://codeforces.com/contest/813/problem/C 题意：一个改版的Tag Game，他就是告诉你一个树状图，然后告诉你点的编号，代表Alice和Bob，每个人可以走到相邻的点或者在原地等，希望Alice尽可能走，Bob希望走较少的步，先是Alice走，求出多少步以后Alice和Bob可以相遇。 思路：从Alice和Bob的点分别出发求最短路，再遍历len数组，找到lena[i]>lenb[i]的所有点，找里面lena[i]的最大值，结果就是lena[i]*2。
#include <iostream> #include <cstring> #include <string> #include <queue> #include <vector> #include <map> #include <algorithm> #define N 200010 #define LL long long #define inf 0x3f3f3f3f using namespace std; vector<int> mapp[N]; bool vis[N]; int len[2][N]; int n; void init() { for (int i = 0; i <= n; i++) { mapp[i].clear(); } memset(len, inf, sizeof(len)); } void spfa(int ans,int cnt) { memset(vis, false, sizeof(vis)); queue<int> q; q.push(ans); vis[ans] = true; len[cnt][ans] = 0; while (!q.empty()) { int u = q.front(); q.pop(); for (int i = 0; i < mapp[u].size(); i++) { int v = mapp[u][i]; if (len[cnt][v] > len[cnt][u] + 1) { len[cnt][v] = len[cnt][u] + 1; if (!vis[v]) { vis[v] = true; q.push(v); } } } vis[u] = false; } } int main() { int a, b; int x; int ans; cin.sync_with_stdio(false); while (cin >> n >> x) { init(); for (int i = 1; i < n; i++) { cin >> a >> b; mapp[a].push_back(b); mapp[b].push_back(a); } spfa(1, 0); spfa(x, 1); ans = 0; for (int i = 1; i <= n; i++) { if (len[0][i] > len[1][i]) { ans = max(ans, len[0][i]); } } cout << ans * 2 << endl; } return 0; }