思路
令 $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;
}