CF1790F题解

思路

令 $dis_i$ 为离 $i$ 最近的黑点距离， $ans$ 是距离最近的一对黑点距离， 我们可以发现， 每次 $i \gets i + 1$ 后 $ans$ 的更新只会与 $dis_{c_i}$ 有关， 因为 $c_i$ 是新的黑点， 然后再从 $c_i$ 来一次 BFS 更新 $dis_i$ 即可。

更详细的在注释。

代码

#include <bits/stdc++.h>

using namespace std;

const int KMaxN = 2e5 + 1;

int n, c[KMaxN], t, u, v, dis[KMaxN]/* 离 i 最近的黑点距离 */, ans = 1e9;
vector<int> g[KMaxN]; // 存边

void bfs(int s) { // 从 s 做一次 BFS 更新
  dis[s] = 0;
  queue<int> q;
  q.push(s);
  while (!q.empty()) {
    int t = q.front();
    q.pop();
    if (dis[t] >= ans) { // 优化：当当前点 i 最近黑点的距离大于最小值 ans, 可以直接不用搜了
      break;
    }
    for (int i : g[t]) {
      if (dis[i] <= dis[t] + 1) {
        continue;
      }
      dis[i] = dis[t] + 1; // 更新
      q.push(i);
    }
  }
}

int main() {
  for (cin >> t; t; t-- , ans = 1e9) { // t 次询问
    cin >> n >> c[0];
    fill(dis + 1 , dis + n + 1 , 1e9);
    for (int i = 1; i < n; i++) {
      g[i].clear();
      cin >> c[i];
    }
    g[n].clear();
    for (int i = 1; i < n; i++) {
      cin >> u >> v;
      g[u].push_back(v);
      g[v].push_back(u);
    }
    bfs(c[0]); // 先对 c[0] 做一次 BFS
    for (int i = 1; i < n; i++) {
      ans = min(ans, dis[c[i]]); // 只有 dis[c[i]] 对 ans 有影响
      cout << ans << " ";
      bfs(c[i]); // 更新 dis
    }
    cout << "\n";
  }
  return 0;
}