[CF1790F] Timofey and Black-White Tree 题解

题目描述

ZYH 有一棵 \(n\) 个节点的树，最初 \(c_0\) 号节点是黑色，其余均为白色。

给定操作序列 \(c_1,c_2,\cdots,c_{n-1}\)，第 \(i\) 次操作表示将 \(c_i\) 号节点染黑。每次操作后，输出距离最近的两个黑点间的距离。两点 \(u,v\) 间的距离定义为 \(u\to v\) 的路径上经过的边的条数。

多组数据，\(1\leq T \leq 10^4,2\leq n \leq 2\times 10^5,\sum n\leq 2\times 10^5\)，节点编号均在 \([1,n]\) 内。

思路

每次加入一个点暴力统计一遍答案，如果当前距离超过了答案就跳出。

这看着好像很暴力，似乎是平方的，但是其实是根号的，由于这个结论：

在一棵树上随机选择 \(\sqrt n\) 个点它们之间的最小距离一定不超过 \(\sqrt n\)。

证明：

对于一条链的情况，最坏情况是 \(n\) 个点隔 \(\sqrt n\)，这种情况下的最小距离最大是 \(\sqrt n\)，而对于一棵树，它是不比链的情况优的。

所以对于前 \(\sqrt n\) 个点，考虑最坏情况，即每次跑 \(n\) 个点，而对于后面 \(n- \sqrt n\) 左右个点，根据前面已经证明过的结论，只要我们一旦超过答案就跳出，它们最多会跑 \(\sqrt n\) 次，这是最坏情况，因此总的时间复杂度是 \(O(n\sqrt n)\)，类似于根号分治。

// Problem: Timofey and Black-White Tree
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF1790F
// Memory Limit: 250 MB
// Time Limit: 4000 ms
// Powered by CP Editor (https://cpeditor.org)
 
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 2e5 + 10;
 
vector<int> g[N];
int q[N], dist[N], ans;
bool vis[N];
inline void bfs(int s) {
    queue<int> q;
    q.push(s);
    dist[s] = 0;
    while(q.size()) {
        int t = q.front();
        q.pop();
        if(dist[t] >= ans) break;
        for(auto v : g[t]) {
            if(dist[v] <= dist[t] + 1) continue;
            dist[v] = dist[t] + 1;
            q.push(v);
        }
    }
}
int n;
inline void work() {
    n = read();
    q[0] = read();
    for(int i = 1; i <= n; i ++) g[i].clear();
    memset(dist, 0x3f, n + 1 << 2);
    for(int i = 1; i < n; i ++) q[i] = read();
    for(int i = 1, a, b; i < n; i ++) {
        a = read(), b = read();
        g[a].push_back(b), g[b].push_back(a);
    }
    ans = n + 1;
    bfs(q[0]);
    for(int i = 1; i < n; i ++) ans = min(ans, dist[q[i]]), bfs(q[i]), write(ans), putchar(' ');
    puts("");
    return ;
}
 
int main() {
    int T = read();
    while(T --) work();
    return 0;
}