BonVoyage - 题解

标签与难度

标签: 树上问题, 深度优先搜索, 线段树, 动态规划, 最长上升子序列, 离线处理难度: 2400

题目大意喵~

哈喵~！各位勇敢的挑战者，我是你们最可靠的我伙伴，准备好和我一起解决这个有趣的树上问题，赚点零花钱（给阿波罗买吃的）了吗？

这道题是这样的：我们有一棵 $n$ 个节点的树，根节点是 1。每个节点 $i$ 都有一个权值 $v[i]$ 。题目定义了一个奇特的 "lili value"，它和一个叫做 "lili sequence" 的东西有关。不过，经过我用爪子一番推导，这个 "lili value" 其实就是一个更广为人知的概念：最长上升子序列（LIS） 的长度！喵~

对于每个节点 $i$ ，它的 lili value 是这么计算的：

给定一个距离系数 $K$ 。
我们找到一条特定的路径：
- 如果节点 $i$ 的深度 $dep[i] \ge K$ ，路径就是从 $i$ 的 $K-1$ 次祖先（一个离 $i$ 距离为 $K-1$ 的祖先节点）到 $i$ 自己。这条路径正好有 $K$ 个节点。
- 如果 $dep[i] < K$ ，路径就是从根节点 1 到 $i$ 。
节点 $i$ 的 lili value 就是这条路径上所有节点的权值所组成的序列的 LIS 长度。

我们的任务是，对于每一个 $K$ （从 1 到 $n$ ），计算出树上有多少个节点的 lili value 大于等于给定的目标值 $W$ 。

解题思路分析

这道题看起来很复杂，要对每个 $K$ 都计算一次，如果暴力模拟，肯定会超时的说！所以我们需要一种更聪明的办法，喵~

核心转换

首先，我们把问题转换一下。对于每个节点 $i$ ，我们不去问“当距离是 $K$ 时，我的 lili value 是否达标？”，而是反过来问：“要让我的 lili value 至少为 $W$ ，我需要的最短路径长度是多少？”

我们定义 $L_i$ 为：以节点 $i$ 为终点，从其某个祖先开始的最短路径，使得该路径的 LIS 长度至少为 $W$ 。假设我们已经为所有节点 $i$ 求出了这个最短路径长度 $L_i$ 。那么对于一个给定的 $K$ ，满足 lili value >= W 的节点 $i$ 就是那些 $L_i \le K$ 的节点。

为什么呢？

如果 $L_i \le K$ ，说明存在一条从 anc(i, L_i-1) 到 i 的路径，其 LIS 长度 $\ge W$ 。当考虑系数 $K$ 时，对应的路径是从 anc(i, K-1) 到 i。这条路径包含了那条长度为 $L_i$ 的路径，所以它的 LIS 长度也必然 $\ge W$ 。
如果 $L_i > K$ ，说明所有以 $i$ 结尾且长度不超过 $K$ 的路径，其 LIS 长度都小于 $W$ 。

所以，我们只需要对每个节点 $i$ 计算出 $L_i$ ，然后统计对于每个 $K$ ，有多少个 $i$ 满足 $L_i \le K$ 。这可以通过一个差分数组或者前缀和来轻松解决：我们创建一个计数数组 counts，对每个计算出的 $L_i$ ，执行 counts[L_i]++。最后，求 counts 的前缀和，prefix_sum[K] 就是当距离系数为 $K$ 时的答案。

如何计算 $L_i$ ？

现在，问题变成了如何高效地计算每个节点的 $L_i$ 。 $L_i$ 的定义是路径长度，路径长度 = dep[i] - dep[祖先] + 1。要让路径长度 $L_i$ 最小，我们需要让起始祖先的深度 dep[祖先] 最大。

所以，对每个节点 $i$ ，我们需要找到深度最大的祖先 $j$ （ $j$ 可以是 $i$ 自己），使得 LIS(path(j, i)) >= W。一旦找到了这个 $j$ ，我们就可以计算出 $L_i = \text{dep}[i] - \text{dep}[j] + 1$ 。

DFS + 线段树魔法！

这个问题可以在一次从根开始的深度优先搜索（DFS）中解决，这就要请出我们强大的魔法工具——线段树啦！

我们用线段树来维护路径上的 LIS 信息。线段树的下标对应的是深度。当我们的 DFS 到达节点 u 时，我们希望线段树能快速告诉我们：对于 u 的任意一个祖先 p_d（深度为 d），路径 p_d -> u 的 LIS 长度是多少。

设 S[d] 为路径 p_d -> u 的 LIS 长度。当 DFS 到达 u 时，我们查询线段树中，满足 S[d] >= W 的最大深度 d_max。这个 d_max 就对应了我们想找的那个深度最大的祖先 $j$ 。于是， $L_u = \text{dep}[u] - d_{max} + 1$ 。

关键在于，当 DFS 从父节点 p 移动到子节点 u 时，如何高效地更新整个线段树？路径从 root -> p 延伸到了 root -> u。对于 u 的所有祖先，它们到 u 的路径都比到 p 的路径多了一个节点 u。这会影响 LIS 的计算。

经过我一番严谨的（爪子乱抓）推导，我们发现 S[d] (即 LIS(path(p_d, u))) 的值等于路径 p_d -> u 上满足特定条件的节点数量。这个条件是：一个节点 x 的“首个值不小于它的祖先”必须是 p_d 的真祖先。这个性质带来了一个神奇的更新方法：当 DFS 到达节点 u 时：

找到分界点祖先：我们先找到 u 的一个祖先 anc，它是 u 最深的祖先且满足 v[anc] >= v[u]。如果不存在这样的祖先，就认为分界点是虚拟的根节点之上。我们可以用另一个辅助数据结构（比如另一个线段树，或者在 DFS 路径上二分）来快速找到 anc。
区间更新：设 anc 的深度为 dep_anc。对于所有深度 d 在 [dep_anc + 1, dep[u]] 区间内的祖先 p_d，它们到 u 的路径的 LIS 长度，恰好都等于它们到 p 的路径的 LIS 长度加一！而其他更深的祖先，它们的 LIS 长度不变。这真是太神奇了，喵！这意味着我们只需要对线段树进行一次区间加一的操作！

所以，完整的算法流程是：

准备一个主线段树 lis_tree，维护 LIS 长度。它的每个节点代表一个深度区间，存储该区间内 LIS 长度的最大值。
准备一个辅助数据结构 val_tree，用于快速查找上述的“分界点祖先”。这个结构也用线段树实现，维护路径上每个深度的节点权值。
从根节点开始 DFS。在节点 u： a. 使用 val_tree 找到 u 的最深祖先 anc，满足 v[anc] >= v[u]。 b. 对 lis_tree 在深度区间 [dep[anc] + 1, dep[u]] 上执行 +1 操作。 c. 在 val_tree 的 dep[u] 位置记录下 v[u]。 d. 查询 lis_tree，找到满足 LIS_length >= W 的最大深度 d_max。 e. 计算 L_u = dep[u] - d_max + 1，并记录下来。 f. 递归访问 u 的所有子节点。 g. 回溯！这是 DFS 的精髓！离开节点 u 前，必须撤销步骤 a, b, c 所做的修改，以保证兄弟分支的计算不受影响。即，在 lis_tree 上执行区间 -1，并清除 val_tree 在 dep[u] 的记录。
DFS 结束后，我们得到了所有节点的 $L_i$ 。
使用一个数组 counts 统计每个 $L_i$ 出现的次数。
计算 counts 数组的前缀和，得到最终答案。

这个方法把复杂的计算分解成了一系列优雅的线段树操作，是不是很酷？喵~

代码实现

这是我根据上面的思路，精心为你准备的全新代码~ 注释超详细的哦！

cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

const int MAXN = 100010;
const int INF = 1e9 + 7;

// --- 图的表示 ---
vector<int> adj[MAXN];
int v_val[MAXN];
int depth[MAXN];
int n, W;

// --- L_i 的结果数组 ---
int min_len_for_W[MAXN];

// --- 主线段树：维护LIS长度 ---
struct LisNode {
    int max_val;
    int lazy_tag;
} lis_tree[MAXN * 4];

// --- 辅助线段树：维护路径上的节点值，用于快速找祖先 ---
struct ValNode {
    int val;
} val_tree[MAXN * 4];

// --- 主线段树操作 ---
void push_up_lis(int node) {
    lis_tree[node].max_val = max(lis_tree[node * 2].max_val, lis_tree[node * 2 + 1].max_val);
}

void push_down_lis(int node) {
    if (lis_tree[node].lazy_tag != 0) {
        lis_tree[node * 2].max_val += lis_tree[node].lazy_tag;
        lis_tree[node * 2].lazy_tag += lis_tree[node].lazy_tag;
        lis_tree[node * 2 + 1].max_val += lis_tree[node].lazy_tag;
        lis_tree[node * 2 + 1].lazy_tag += lis_tree[node].lazy_tag;
        lis_tree[node].lazy_tag = 0;
    }
}

void build_lis(int node, int l, int r) {
    lis_tree[node].max_val = 0;
    lis_tree[node].lazy_tag = 0;
    if (l == r) return;
    int mid = (l + r) / 2;
    build_lis(node * 2, l, mid);
    build_lis(node * 2 + 1, mid + 1, r);
}

void update_lis(int node, int l, int r, int ql, int qr, int val) {
    if (ql > qr) return;
    if (ql <= l && r <= qr) {
        lis_tree[node].max_val += val;
        lis_tree[node].lazy_tag += val;
        return;
    }
    push_down_lis(node);
    int mid = (l + r) / 2;
    if (ql <= mid) {
        update_lis(node * 2, l, mid, ql, qr, val);
    }
    if (qr > mid) {
        update_lis(node * 2 + 1, mid + 1, r, ql, qr, val);
    }
    push_up_lis(node);
}

int query_lis(int node, int l, int r) {
    if (lis_tree[node].max_val < W) {
        return 0; // 0 表示没找到
    }
    if (l == r) {
        return l;
    }
    push_down_lis(node);
    int mid = (l + r) / 2;
    if (lis_tree[node * 2 + 1].max_val >= W) {
        return query_lis(node * 2 + 1, mid + 1, r);
    }
    return query_lis(node * 2, l, mid);
}

// --- 辅助线段树操作 ---
void build_val(int node, int l, int r) {
    val_tree[node].val = -1; // -1 表示该深度无节点
    if (l == r) return;
    int mid = (l + r) / 2;
    build_val(node * 2, l, mid);
    build_val(node * 2 + 1, mid + 1, r);
}

void update_val(int node, int l, int r, int pos, int val) {
    if (l == r) {
        val_tree[node].val = val;
        return;
    }
    int mid = (l + r) / 2;
    if (pos <= mid) {
        update_val(node * 2, l, mid, pos, val);
    } else {
        update_val(node * 2 + 1, mid + 1, r, pos, val);
    }
    val_tree[node].val = max(val_tree[node*2].val, val_tree[node*2+1].val);
}

int query_val(int node, int l, int r, int ql, int qr, int target_val) {
    if (ql > qr || val_tree[node].val < target_val) {
        return 0; // 0 表示没找到
    }
    if (l == r) {
        return l;
    }
    int mid = (l + r) / 2;
    int res = 0;
    // 优先在更深（右边）的区间找
    if (qr > mid) {
        res = query_val(node * 2 + 1, mid + 1, r, ql, qr, target_val);
    }
    if (res != 0) return res;
    if (ql <= mid) {
        res = query_val(node * 2, l, mid, ql, qr, target_val);
    }
    return res;
}

// --- 核心DFS ---
void dfs(int u, int p, int d) {
    depth[u] = d;

    // 1. 找到分界点祖先的深度
    int ancestor_depth = query_val(1, 1, n, 1, d - 1, v_val[u]);
    
    // 2. 更新主线段树
    update_lis(1, 1, n, ancestor_depth + 1, d, 1);
    
    // 3. 更新辅助线段树
    update_val(1, 1, n, d, v_val[u]);
    
    // 4. 查询 LIS>=W 的最深祖先
    int max_d = query_lis(1, 1, n);
    if (max_d > 0) {
        min_len_for_W[u] = d - max_d + 1;
    } else {
        min_len_for_W[u] = n + 1; // 标记为不可能
    }

    // 5. 递归
    for (int neighbor : adj[u]) {
        if (neighbor != p) {
            dfs(neighbor, u, d + 1);
        }
    }

    // 6. 回溯，撤销修改
    update_lis(1, 1, n, ancestor_depth + 1, d, -1);
    update_val(1, 1, n, d, -1);
}

void solve() {
    cin >> n >> W;
    for (int i = 1; i <= n; ++i) {
        cin >> v_val[i];
        adj[i].clear();
    }
    for (int i = 0; i < n - 1; ++i) {
        int u_node, v_node;
        cin >> u_node >> v_node;
        adj[u_node].push_back(v_node);
        adj[v_node].push_back(u_node);
    }

    build_lis(1, 1, n);
    build_val(1, 1, n);

    dfs(1, 0, 1);

    vector<int> counts(n + 2, 0);
    for (int i = 1; i <= n; ++i) {
        if (min_len_for_W[i] <= n) {
            counts[min_len_for_W[i]]++;
        }
    }

    for (int i = 1; i <= n; ++i) {
        counts[i] += counts[i - 1];
    }

    for (int i = 1; i <= n; ++i) {
        cout << counts[i] << (i == n ? "" : " ");
    }
    cout << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析

时间复杂度: $O(N \log N)$ 我们对整棵树进行了一次深度优先搜索，总共访问了 $N$ 个节点。在每个节点，我们执行了若干次线段树操作（更新和查询）。线段树的深度是 $O(\log N)$ ，所以每次操作的复杂度是 $O(\log N)$ 。因此，总的时间复杂度是 $O(N \log N)$ 。
空间复杂度: $O(N)$ 我们需要存储树的邻接表，大约是 $O(N)$ 的空间。两个线段树都需要 $4N$ 大小的数组，所以也是 $O(N)$ 。深度、权值等辅助数组同样是 $O(N)$ 。总的空间复杂度是 $O(N)$ 。

知识点总结

这道题是多种算法思想的巧妙结合，能解决它说明你超棒的，喵！

问题转换: 将对每个 $K$ 的查询，转化为对每个节点求一个最优值 $L_i$ ，再离线处理所有查询。这是处理多查询问题的常用技巧。
Lili Value 与 LIS: 识别出题目中看似复杂的定义背后是经典的 LIS 模型，是解题的关键突破口。
树上路径问题与DFS: 将对树上大量路径的计算，通过一次 DFS 遍历来完成。DFS 过程中的“路径”信息是动态变化的，非常适合用数据结构来维护。
线段树维护动态信息: 线段树在这里扮演了核心角色。它不仅仅是用来做静态区间的查询，更重要的是，它在 DFS 的过程中动态地维护了从各个祖先到当前节点的 LIS 长度信息。
DFS中的回溯: 在递归函数返回前，必须撤销对全局数据结构（线段树）的修改，这是保证算法正确性的重要一环。

希望这篇题解能帮到你！如果还有不明白的地方，随时可以再来问我哦~ 祝你刷题愉快，喵~！

BonVoyage - 题解 ​

标签与难度 ​

题目大意喵~ ​

解题思路分析 ​

核心转换 ​

如何计算 LiL_iLi​？ ​

DFS + 线段树魔法！ ​

代码实现 ​

复杂度分析 ​

知识点总结 ​