「JOI 2023 Final」训猫 题解

题目大意

给定一棵 $N$ 个节点的树，每个节点有一个唯一的高度 $P_i$（1 到 $N$ 的排列）。初始时猫在高度为 $N$ 的节点上。通过放置障碍物的策略，使得猫按照特定规则移动，求猫的总移动距离的最大值。

解题思路

核心算法：树链剖分 + 并查集 + 动态规划

该解法使用了一种巧妙的逆向处理策略，从低高度节点向高高度节点处理，利用并查集维护连通块信息。

关键步骤

1. 输入预处理

for (int i = 1; i < n; ++i) {
    int u, v;
    cin >> u >> v;
    adj[a[u]].push_back(a[v]);  // 按高度值建图
    adj[a[v]].push_back(a[u]);
}

• 将输入的节点编号转换为高度值建图
• 这样图中的节点1对应高度1，节点N对应高度N

2. 树链剖分预处理

void predfs(int u, int par) {
    // 计算子树大小，找重儿子
    bc[u] = -1;  // 重儿子
    sz[u] = 1;   // 子树大小
    // ...
}

void hld(int u) {
    // 树链剖分，将树分解为链
    // hepa[cntpa]：每条链的顶端节点
    // idpa[u]：节点u所在的链编号
}

3. 逆向动态规划

for (int i = 2; i <= n; ++i) {
    for (int v : adj[i]) {
        if (v > i) continue;  // 只处理高度较低的邻居
        int x = findset(v);
        int y = findset(i);
        if (x != y) {
            dp[i] = max(dp[mx[x]] + cost(mx[x], i), dp[i]);
            unite(x, y);
        }
    }
}

算法原理

核心思想

• 逆向处理：从高度1到高度N依次处理节点
• 并查集维护：每个连通块记录该块中最高高度的节点
• 状态转移：dp[i] 表示猫到达高度i的节点时的最大移动距离

状态转移方程

对于节点i，检查所有高度小于i的邻居v：

dp[i] = max{ dp[mx[findset(v)]] + dist(mx[findset(v)], i) }

其中：

• mx[findset(v)]：v所在连通块中高度最大的节点
• dist(u, v)：节点u到v的树上距离

关键函数

LCA计算树上距离

int lca(int u, int v) {
    // 使用树链剖分快速求LCA
    while (idpa[u] != idpa[v]) {
        if (idpa[u] > idpa[v]) u = p[hepa[idpa[u]]];
        else v = p[hepa[idpa[v]]];
    }
    return dep[u] < dep[v] ? u : v;
}

ll cost(int u, int v) {
    return dep[u] + dep[v] - 2 * dep[lca(u, v)];  // 树上距离
}

并查集操作

int findset(int u) {
    return lab[u] < 0 ? u : lab[u] = findset(lab[u]);
}

void unite(int u, int v) {
    if (lab[u] > lab[v]) swap(u, v);
    lab[u] += lab[v];
    mx[u] = max(mx[u], mx[v]);  // 维护连通块中最大高度
    lab[v] = u;
}

算法正确性分析

为什么这样设计？

1. 逆向处理的直觉：

   • 猫总是向更高处移动
   • 从低处向高处处理，可以累积移动距离

2. 并查集的作用：

   • 维护已经处理过的连通区域
   • 每个连通块记录能到达的最高点

3. dp状态的意义：

   • dp[i] 表示猫第一次到达高度i时的累计移动距离
   • 通过合并连通块，找到到达i的最优路径

时间复杂度

• 树链剖分：$O(N)$
• LCA查询：$O(\log N)$
• 整体算法：$O(N \log N)$

样例验证

样例1分析：

节点高度：3,4,1,2
树结构：1-2-3-4

处理过程：
- 节点1：初始化
- 节点2：连接到节点1，计算距离
- 节点3：连接到节点2，计算距离  
- 节点4：连接到节点3，计算距离
最终dp[4] = 3

代码亮点

1. 高度重标号：将节点按高度值重新编号，简化处理
2. 树链剖分：高效计算树上距离
3. 逆向DP：从低到高处理，符合猫的移动特性
4. 并查集优化：维护连通块信息，避免重复计算

总结

这个解法通过巧妙的逆向处理和并查集维护，将复杂的障碍物放置问题转化为经典的树形动态规划问题。关键在于：

1. 问题转化：将障碍物策略转化为路径规划
2. 数据结构选择：树链剖分求LCA，并查集维护连通性
3. 状态设计：dp[i]表示到达高度i的最大移动距离

该算法在 $N \leq 2 \times 10^5$ 的数据规模下能够高效运行，是一个优秀的解决方案。