每日一题：Playing Tag on Tree

题意

给定一棵树，A 在 $x$ 点，B 在 $y$ 点，B 追 A，两人每次可以往相邻点移动，A 先跑，问 A 最晚什么时候被追上。

Solution

结论：找到一个点，满足 $dis_B > dis_A$ 且 $dis_B$ 最大，即为最终落脚点。

因为直观上来说，明显最后的点离 B 越远越好，但这个点可能离 A 更远，因此需要满足 $dis_B > dis_A$。

Code

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int dis[2][N];
vector<int> g[N];

void bfs(int be, int id) {
  queue<int> q;
  q.push(be);
  dis[id][be] = 1;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (auto v : g[u]) {
      if (!dis[id][v]) {
        dis[id][v] = dis[id][u] + 1;
        q.push(v);
      }
    }
  }
}

int main() {
  int n, x, y, u, v, res = 0;
  cin >> n >> x >> y;
  for (int i = 1; i < n; i++) {
    cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  bfs(x, 0);
  bfs(y, 1);
  for (int i = 1; i <= n; i++) {
    if (dis[0][i] < dis[1][i]) res = max(res, dis[1][i] - 2);
  }
  cout << res << endl;
  return 0;
}