P5912 [POI2004]JAS

Alex_Wei · 2021-11-03 16:33:02 · 题解

*I. P5912 [POI2004]JAS

摘自 贪心专题 第三部分例题 I.

究极神仙题。

首先对问题进行转化：相当于我们需要求原树最浅的一个点分树深度。假设点 i 在倒数第 d_i+1 次被问到，那么任意两个 d 值相同的点 u,v 之间的简单路径必然存在一个点 a 使得 d_a>d_u，因为这样才能使它们进入不同的点分树子树，说人话即 a 是深度相同的点 u,v 在点分树上的 LCA（的祖先）。

考虑这样一个贪心：我们记 S_i 表示 i 的子树内所有可能不满足条件的 d 值，即存在 u\in \mathrm{subtree}(i) 使得不存在 v\in \mathrm{path}(u,i) 满足 d_v>d_u 的所有 d_u 的集合，以二进制状压形式存储。合并 i 的两个子树 u,v 时，首先 d_i 应大于任何一个既在 S_u 又在 S_v 内的元素，否则显然不合法。此外，d_i 还不应存在于 S_u 和 S_v 中，我们选择所有满足条件的最小的 d_i 即可。S_i 即所有 S_u 与 \{d_i\} 的并去掉所有 <d_i 的元素后的集合。

根据点分树的结论答案不可能超过 \log n，因此时间复杂度 \mathcal{O}(n\log n)，可以做到线性：通过位运算我们求出可行的 d_i 集合，取 \mathrm{lowbit} 即可，拿到了最优解。

const int N = 5e4 + 5;
const int K = 1 << 16; 
int cnt, hd[N], nxt[N << 1], to[N << 1];
void add(int u, int v) {nxt[++cnt] = hd[u], hd[u] = cnt, to[cnt] = v;}
int n, f[N], S[N], lg[K], buc[K];
void dfs(int id, int fa) {
    int msk = 0, ban = 0, leaf = 1;
    for(int i = hd[id]; i; i = nxt[i]) {
        int it = to[i];
        if(it == fa) continue;
        leaf = 0, dfs(it, id), f[id] = max(f[id], f[it]);
        msk |= ban & S[it], ban |= S[it];
    } if(leaf) return S[id] = 1, void();
    msk = (K - (1 << lg[msk])) & (K - 1 - ban);
    int c = !msk ? lg[n] + 1 : buc[msk & -msk];
    f[id] = max(f[id], c);
    S[id] = (ban & (K - (1 << c))) | (1 << c);
}

int main(){
    cin >> n;
    for(int i = 2; i < K; i++) lg[i] = lg[i >> 1] + 1;
    for(int i = 1; i < 16; i++) buc[1 << i] = i;
    for(int i = 1; i < n; i++) {
        int u = read(), v = read();
        add(u, v), add(v, u);
    } dfs(1, 0), cout << f[1] << endl;
    return 0;
}

启示：遇到无从下手的问题时先尝试抽象问题并分析性质（本题中是两点间的简单路径必然存在点分树的 LCA）使其更好理解。树上问题先从叶子开始，可以先考虑一些简单情况再尝试总结策略。树形 DP 先考虑仅合并两个子树的情况。