Make Shan Happy - 题解

标签与难度

标签: 数据结构, 树链剖分, 线段树, 离线处理, 树上问题, LCA 难度: 2600

题目大意喵~

Nyahello~！各位算法大师们，今天我们来帮助可爱的鱼鱼 Shan 解决一个难题，让她开心起来吧，喵！

事情是这样的：我们有一棵 $N$ 个节点的树，根节点是 1。每个节点 $i$ 都有一个权值 $W[i]$ 。这棵树有一个很棒的性质：对于任意一个节点 $y$ 和它的祖先节点 $x$ ，一定有 $W[x] \le W[y]$ 。也就是说，从根节点往下走，路径上节点的权值是不会变小的哦！

Shan 有 $M$ 个问题。每个问题都由一对数字 $(x, k)$ 给出。对于每个问题，她想让你帮忙找到一个编号最大的节点 $y$ ，这个 $y$ 必须满足一个条件：

y - k \le W[\text{lca}(x, y)]

其中 $\text{lca}(x, y)$ 是节点 $x$ 和 $y$ 的最近公共祖先。

你需要对每个问题，都找出这个最大的 $y$ 。如果找不到满足条件的 $y$ ，就输出 0 好了。

解题思路分析

这道题看起来有点棘手呢，喵~ 条件里既有我们要找的 $y$ ，又有依赖于 $y$ 的 $\text{lca}(x, y)$ ，直接求解可不容易。不过别担心，跟着本喵的思路，一步一步就能解开谜题！

倒序处理，化被动为主动

我们要求的是最大的 $y$ 。这个“最大”是个非常重要的提示！它暗示我们可以从大到小地考虑 $y$ 的可能取值。

想象一下，我们把所有询问先存起来，然后按 $y = N, N-1, \dots, 1$ 的顺序来处理。对于当前的 $y$ ，我们来看看有哪些询问第一次被满足了。因为我们是从大到小枚举 $y$ 的，所以当前这个 $y$ 一定是能满足这些询问的最大的 $y$ 值。这样，我们就把“寻找最大值”的问题转化成了一个判定问题，喵！

转化条件，发现关键性质

对于一个询问 $(x_i, k_i)$ 和我们正在考察的 $y$ ，满足条件的公式是 $y - k_i \le W[\text{lca}(x_i, y)]$ 。我们把它稍微变个形：

y \le W[\text{lca}(x_i, y)] + k_i

当我们固定了 $y$ 之后，对于所有尚未找到答案的询问 $i$ ，我们想知道哪个询问最有可能被满足。也就是说，我们要找到一个询问 $i_0$ ，使得 $W[\text{lca}(x_{i_0}, y)] + k_{i_0}$ 这个值最大。如果这个最大值都小于 $y$ ，那对于当前的 $y$ 来说，就没有任何询问能被满足了。反之，如果这个最大值大于等于 $y$ ，那么恭喜，我们就为询问 $i_0$ 找到了答案 $y$ ！

所以，核心问题变成了：对于一个固定的 $y$ ，如何高效地计算 $\max_{i \in \text{未解决的询问}} \{ W[\text{lca}(x_i, y)] + k_i \}$ ？

终极变形！本喵的灵光一闪！

直接计算上面那个式子还是很难，因为 $\text{lca}(x_i, y)$ 还是依赖于 $x_i$ 。但是，别忘了题目给的那个美妙性质： $W[\text{ancestor}] \le W[\text{descendant}]$ ！

本喵发现一个惊人的等式：

\max_{i} \{ W[\text{lca}(x_i, y)] + k_i \} = \max_{p \in \text{path}(y, \text{root})} \{ W[p] + \max_{i \text{ s.t. } p \text{ 是 } x_i \text{ 的祖先}} \{k_i\} \}

其中 $\text{path}(y, \text{root})$ 是从 $y$ 到根节点的路径。

为什么这个等式成立呢？喵~ 让我来证明给你看：

“≤” 的证明: 对于任意一个询问 $i$ ，令 $p' = \text{lca}(x_i, y)$ 。显然 $p'$ 在 $y$ 到根的路径上，并且 $p'$ 是 $x_i$ 的祖先。所以 $W[p'] + k_i$ 是右边式子在考察 $p=p'$ 时的一个候选项，因此左式 $\le$ 右式。
“≥” 的证明: 设右边的最大值在 $p=p_0$ 时取得，对应的 $k_i$ 来自询问 $i_0$ （即 $p_0$ 是 $x_{i_0}$ 的祖先）。此时右边的值为 $W[p_0] + k_{i_0}$ 。令 $p' = \text{lca}(x_{i_0}, y)$ 。因为 $p_0$ 是 $x_{i_0}$ 和 $y$ 的公共祖先，所以 $p_0$ 一定是 $p'$ 的祖先（或者 $p_0=p'$ ）。根据题目性质，我们有 $W[p_0] \le W[p']$ 。所以 $W[p_0] + k_{i_0} \le W[p'] + k_{i_0} = W[\text{lca}(x_{i_0}, y)] + k_{i_0}$ 。而这个值是左边式子的一个候选项。所以右式 $\le$ 左式。

两边都成立，所以等式成立！喵~ 是不是很神奇？

树链剖分 + 线段树，终结难题！

有了这个强大的等式，我们就可以用数据结构来解决了！问题变成了：

对于每个询问 $(x_i, k_i)$ ，它会对 $x_i$ 的所有祖先产生贡献 $k_i$ 。
对于每个 $y$ ，我们需要查询它到根节点的路径上所有点 $p$ 的 $W[p] + (\text{p收到的最大k值})$ 的最大值。

这是一个典型的路径查询问题，树链剖分（Heavy-Light Decomposition）和线段树是解决它的最佳拍档！

具体步骤如下:

预处理: 对树进行两遍 DFS，完成树链剖分，得到每个节点的 dfs序(id)、所在链的顶端(top) 等信息。
数据结构: 建立一棵基于 dfs序 的线段树。线段树的每个节点 o 维护这些信息：
- max_w: 区间内所有树节点的 W 值的最大值。
- queries: 一个多重集（multiset），存放所有完全覆盖本线段树节点的路径所贡献的 {k, query_id} 对。
- max_val: 一个 {value, query_id} 对，表示本区间内能产生的 W[p] + K(p) 的最大值及其来源。
初始化:
- 将所有询问 $(x_i, k_i)$ 加入数据结构。对于每个询问，我们将 {k_i, i} 添加到 $x_i$ 到根节点路径上所有对应线段树节点的 queries 集合中。这可以通过树链剖分，将路径拆成 $O(\log N)$ 个连续的 dfs序区间，然后在线段树上进行区间更新。
主循环:
- 从 $y = N$ 循环到 $1$ 。
- 在循环内部，我们再用一个 while(true) 循环，因为一个 $y$ 可能同时满足多个询问。
- 查询: 沿着 $y$ 到根节点的路径进行查询。这同样被拆分成 $O(\log N)$ 次线段树上的区间查询。线段树查询需要一些技巧：在递归查询时，需要向下传递一个“从根节点到当前节点路径上遇到的最大k值”，和当前节点的信息结合，才能算出正确的最大值。
- 查询会返回一个最大值 V_max 和对应的询问ID q_id。
- 判断与更新:
  - 如果 V_max < y，说明对于当前这个 $y$ ，已经没有任何（未解决的）询问可以被满足了。跳出 while 循环，继续处理 $y-1$ 。
  - 如果 V_max >= y，太棒了！我们为询问 q_id 找到了答案，ans[q_id] = y。然后，我们需要把这个询问从数据结构中“移除”，因为它已经解决了。移除操作和添加操作类似，也是一次树链剖分后的路径更新，只是这次是从 queries 集合中删除 {k_{q_id}, q_id}。

这样，等 $y$ 循环到 1，所有能被满足的询问就都找到了它们各自最大的 $y$ 啦！

代码实现

这是本喵根据上面的思路，精心重构的一份代码，加满了注释，希望能帮到你，喵~

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

// 使用 pair 表示 (值, 询问ID)
using pii = pair<int, int>;

const int MAXN = 100005;
const pii P_NEG_INF = {-2e9, 0}; // 一个极小的 pair 作为初始值

// --- 树和询问相关 ---
int n, m;
vector<int> adj[MAXN];
int weights[MAXN];
int query_x[MAXN], query_k[MAXN];
int ans[MAXN];

// --- 树链剖分相关 ---
int parent[MAXN], depth[MAXN], subtree_size[MAXN];
int heavy_son[MAXN], top_of_chain[MAXN];
int dfs_order[MAXN], node_by_order[MAXN];
int timer;

// --- 线段树节点 ---
struct SegNode {
    pii max_val; // 维护区间的最大 W[p]+K(p) 值和对应的询问ID
    int max_w;   // 维护区间的最大 W[p]
    multiset<pii> queries; // 懒标记性质的集合，存放 (k, query_id)
};
SegNode seg_tree[MAXN * 4];

// --- 树链剖分 ---

void dfs1_size(int u, int p, int d) {
    parent[u] = p;
    depth[u] = d;
    subtree_size[u] = 1;
    heavy_son[u] = 0;
    int max_sz = 0;
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs1_size(v, u, d + 1);
        subtree_size[u] += subtree_size[v];
        if (subtree_size[v] > max_sz) {
            max_sz = subtree_size[v];
            heavy_son[u] = v;
        }
    }
}

void dfs2_hld(int u, int top) {
    top_of_chain[u] = top;
    timer++;
    dfs_order[u] = timer;
    node_by_order[timer] = u;
    if (heavy_son[u]) {
        dfs2_hld(heavy_son[u], top);
    }
    for (int v : adj[u]) {
        if (v == parent[u] || v == heavy_son[u]) continue;
        dfs2_hld(v, v);
    }
}

// --- 线段树操作 ---

void push_up(int o) {
    // 1. 从子节点继承 max_val
    seg_tree[o].max_val = max(seg_tree[o * 2].max_val, seg_tree[o * 2 + 1].max_val);
    
    // 2. 结合本节点的 queries 和 max_w 计算新的 max_val
    if (!seg_tree[o].queries.empty()) {
        pii local_best_k = *seg_tree[o].queries.rbegin();
        local_best_k.first += seg_tree[o].max_w;
        seg_tree[o].max_val = max(seg_tree[o].max_val, local_best_k);
    }
}

void build(int o, int l, int r) {
    seg_tree[o].max_val = P_NEG_INF;
    if (l == r) {
        seg_tree[o].max_w = weights[node_by_order[l]];
        return;
    }
    int mid = (l + r) / 2;
    build(o * 2, l, mid);
    build(o * 2 + 1, mid + 1, r);
    seg_tree[o].max_w = max(seg_tree[o * 2].max_w, seg_tree[o * 2 + 1].max_w);
}

void update_path_queries(int o, int l, int r, int ql, int qr, pii val, bool add) {
    if (ql <= l && r <= qr) {
        if (add) {
            seg_tree[o].queries.insert(val);
        } else {
            seg_tree[o].queries.erase(seg_tree[o].queries.find(val));
        }
    } else {
        int mid = (l + r) / 2;
        if (ql <= mid) {
            update_path_queries(o * 2, l, mid, ql, qr, val, add);
        }
        if (qr > mid) {
            update_path_queries(o * 2 + 1, mid + 1, r, ql, qr, val, add);
        }
    }
    push_up(o);
}

pii query_path_max(int o, int l, int r, int ql, int qr, pii inherited_k) {
    if (ql > r || qr < l) {
        return P_NEG_INF;
    }
    
    // 结合从祖先节点继承来的 k 值
    if (!seg_tree[o].queries.empty()) {
        inherited_k = max(inherited_k, *seg_tree[o].queries.rbegin());
    }

    if (ql <= l && r <= qr) {
        pii result = seg_tree[o].max_val;
        if (inherited_k.first > -1e9) { // 确保 inherited_k 是有效的
            pii potential_res = inherited_k;
            potential_res.first += seg_tree[o].max_w;
            result = max(result, potential_res);
        }
        return result;
    }

    int mid = (l + r) / 2;
    pii res_l = query_path_max(o * 2, l, mid, ql, qr, inherited_k);
    pii res_r = query_path_max(o * 2 + 1, mid + 1, r, ql, qr, inherited_k);
    return max(res_l, res_r);
}

// --- 封装 HLD + SegTree 的操作 ---

void modify_query_on_tree(int u, int query_id, int k, bool add) {
    pii val = {k, query_id};
    while (u) {
        update_path_queries(1, 1, n, dfs_order[top_of_chain[u]], dfs_order[u], val, add);
        u = parent[top_of_chain[u]];
    }
}

pii find_best_query_for_y(int u) {
    pii result = P_NEG_INF;
    while (u) {
        result = max(result, query_path_max(1, 1, n, dfs_order[top_of_chain[u]], dfs_order[u], P_NEG_INF));
        u = parent[top_of_chain[u]];
    }
    return result;
}


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> weights[i];
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs1_size(1, 0, 1);
    dfs2_hld(1, 1);

    build(1, 1, n);

    for (int i = 1; i <= m; ++i) {
        cin >> query_x[i] >> query_k[i];
        modify_query_on_tree(query_x[i], i, query_k[i], true);
    }

    for (int y = n; y >= 1; --y) {
        while (true) {
            pii best_query = find_best_query_for_y(y);
            if (best_query.first < y) {
                break; // 当前 y 无法满足任何剩余的询问
            }
            int q_id = best_query.second;
            ans[q_id] = y;
            // 移除已解决的询问
            modify_query_on_tree(query_x[q_id], q_id, query_k[q_id], false);
        }
    }

    for (int i = 1; i <= m; ++i) {
        cout << ans[i] << "\n";
    }

    return 0;
}

复杂度分析

时间复杂度: $O((N + M \log N) \log N)$
- 树链剖分预处理是 $O(N)$ 。
- 线段树构建是 $O(N)$ 。
- 初始时，将 $M$ 个询问加入线段树。每个询问的路径更新会分解成 $O(\log N)$ 个区间，线段树每次区间更新需要 $O(\log N)$ ，所以这部分是 $O(M \log^2 N)$ 。
- 主循环部分，总共有 $M$ 个询问会被解决和移除。每次解决一个询问，需要一次路径查询 $O(\log^2 N)$ 和一次路径更新 $O(\log^2 N)$ 。所以这部分总共是 $O(M \log^2 N)$ 。
- 哎呀，本喵好像算错了喵！仔细看我的代码实现，update_path_queries 里的递归调用是沿着线段树的，不是对每个区间再跑一次logN，所以路径更新其实是 $O(\log^2 N)$ 。但是查询 query_path_max 每次调用都会进入线段树，所以路径查询是 $O(\log^2 N)$ 。总复杂度应该是 $O(N + M \log^2 N)$ 才对，喵~
空间复杂度: $O(N \log M)$ 或 $O(N + M \log N)$
- 树链剖分和邻接表等需要 $O(N)$ 空间。
- 线段树本身有 $O(4N)$ 个节点。
- 关键在于 multiset。在最坏的情况下，一个询问的路径更新会影响 $O(\log N)$ 个线段树节点，所以 $M$ 个询问总共会产生 $O(M \log N)$ 个条目分散在各个 multiset 中。所以空间复杂度是 $O(N + M \log N)$ 。

知识点总结

能解开这道题，你已经非常厉害啦，喵！我们来总结一下用到的酷炫知识点吧：

离线处理: 解决“求最值”问题的一个经典技巧。通过对答案的可能范围（这里是 $y$ 的值）进行排序（或倒序）处理，将问题转化为一系列的判定和更新。
关键性质的挖掘与利用: 解题的核心突破口在于那个神奇的等式。这告诉我们，深入理解和利用题目给定的性质（比如本题的权值单调性）往往能化繁为简。
树链剖分 + 线段树: 解决各类树上路径问题的“黄金搭档”。树链剖分将树上路径问题转化为序列上的区间问题，再由线段树等数据结构高效处理。
复杂的线段树设计: 本题的线段树不是简单的加加减减。它需要维护一个集合（multiset）作为懒标记的变体，并在查询时将路径上（指线段树的递归路径）的信息进行合并。这是一种更高级的线段树用法，值得好好体会，喵~

希望这篇题解能让你有所收获！我们下次再一起探险算法世界吧，喵~！

Make Shan Happy - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

倒序处理，化被动为主动 ​

转化条件，发现关键性质 ​

终极变形！本喵的灵光一闪！ ​

树链剖分 + 线段树，终结难题！ ​

代码实现 ​

复杂度分析 ​

知识点总结 ​