原题传送门 分别以 A , B A,B A,B为起点遍历一遍求出树上各点与 A , B A,B A,B的距离 d i s a i , d i s b i disa_i,disb_i disai,disbi B B B希望久一点， A A A希望快一点 那么枚举点 i i i，若 d i s b i > = d i s a i disb_i>=disa_i disbi>=disai，说明之前 B B B肯定被 A A A抓到了 所以对于所有的 d i s b i < d i s a i disb_i<disa_i disbi<disai，答案是 m a x ( 2 d i s a i ) max(2disa_i) max(2disai)
Code：
#include <bits/stdc++.h> #define maxn 200010 using namespace std; struct Edge{ int to, next; }edge[maxn << 1]; int num, head[maxn], f[maxn][2], n, a, b; inline int read(){ int s = 0, w = 1; char c = getchar(); for (; !isdigit(c); c = getchar()) if (c == '-') w = -1; for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48); return s * w; } void addedge(int x, int y){ edge[++num] = (Edge){y, head[x]}, head[x] = num; } void dfs(int u, int pre, int s, int opt){ f[u][opt] = s; for (int i = head[u]; i; i = edge[i].next){ int v = edge[i].to; if (v != pre) dfs(v, u, s + 1, opt); } } int main(){ n = read(), b = read(), a = 1; for (int i = 1; i < n; ++i){ int x = read(), y = read(); addedge(x, y), addedge(y, x); } dfs(1, 0, 0, 1); dfs(b, 0, 0, 2); int ans = 0; for (int i = 2; i <= n; ++i) if (f[i][2] < f[i][1]) ans = max(ans, f[i][1]); printf("%d\n", ans << 1); return 0; }