题解：P16356 「Diligent-OI R3 D」神秘树

HoshinoIchika · 2026-04-26 17:47:57 · 题解

爆标爽。

考虑证明一个结论：对于任意正整数 x, y, z，若 y > \frac x2，则 x \bmod y + y \bmod z \ge x \bmod z。

证明是简单的：

• 若 y > x，则 x \bmod y = x \ge x \bmod z。
• 若 \frac x2 < y \le x，有 x \bmod y = x - y。而显然 x \bmod z - y \bmod z \le x - y。

那么对于一个结点序列 v，(v_{i - 1}, v_i) 之间如果存在一个点 p 满足 a_p > \frac{a_{v_{i - 1}}} 2，将 p 插入到结点序列不会导致答案变劣。所以可以规定这样的转移不合法。

考虑链怎么做。维护一个类似单调队列的东西，每次：

• 暴力枚举队内的点向点 i 转移；
• 把队头 a_j < 2a_i 的点 j 弹出；
• 把队尾距离不合法的点弹出；
• 然后将点 i 入队。

队列中相邻的两个点 x, y 满足 a_x \ge 2a_y，所以队列大小是 \mathcal{O}(\log V) 的。那么可以直接把链上的做法移到树上并且暴力撤销所有操作，时间复杂度仍为 \mathcal{O}(n \log V)。

::::info[参考实现]

void dp(int u, int fa, deque<int> q){
    while (q.size() && de[q.front()] < de[u] - k) q.pop_front();
    for (int x : q) tmax(f[u], f[x] + a[x] % a[u]);
    while (q.size() && a[q.back()] < a[u] << 1) q.pop_back();
    q.push_back(u), tmax(ans, f[u]);
    for (int i = G.h(u);i != -1;i = G[i].nxt){
        int v = G[i].v;if (v == fa) continue;
        de[v] = de[u] + 1, dp(v, u, q);
    }
}

::::