专栏文章

题解：P9352 [JOI 2023 Final] 训猫 / Cat Exercise

MMrkn_chenyx12
P9352题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@mio6uq1t
此快照首次捕获于
2025/12/02 14:19
3 个月前
此快照最后确认于
2025/12/02 14:19
3 个月前
查看原文

题意转化

不难发现，仅有在猫所在的塔上放置障碍可以使猫移动。障碍会把塔组成的树（或其中的某一连通块）划分为若干新的更小规模的连通块，猫只能进入其中之一，且合理地放置障碍可以使得猫进入任何新连通块的最高点。同时，最优的方案一定可以是每次移动都前往某一新连通块的最高点。
由此，将问题转化为求从最高点出发，不断前往划分出的若干连通块之一的最高点直到无法移动所经过的最长路径。

解题思路

以最高点为根进行深度优先搜索，构建较低点指向较高点的新树。考虑如果已知某个节点 uu 的所有子树生成的新树后如何合并，手玩一些小数据可以得知：
  1. 对于所有在原树上到 uu 的路径上有高度大于自身高度的节点，指向不会发生变化。
  2. 某棵子树中所有不符合第一条且高度小于 uu 的高度的点中，最高的点改为指向 uu。
  3. uu 和所有子树中所有不符合第一条且高度大于 uu 的高度的点中，从小到大构成一条链。
如果某个点在以 uu 为根的子树中是第二类点，则在以 uu 的父节点为根的子树中必然是第一类点，且所有第一类点必然在一颗规模更小的子树中是第二类点。由此，考虑使用可并堆维护所有尚不满足第一条的节点，对于每颗子树处理所有第二类点并移出可并堆，uu 和剩余部分并为新的可并堆并返回。
考虑延迟处理第三类点，当其首次成为第二类点时进行处理。最终仍然会剩下一些第三类点，也需要处理。
该部分时间复杂度为 O(nlog⁡n)O(n\log n)。
新树构建完成后，只需要知道相邻两点在原树中的距离即可求出答案，即从根节点出发的最长路径长度。考虑使用倍增法，时间复杂度 O(nlog⁡n)O(n\log n)。
总体时间复杂度 O(nlog⁡n)O(n\log n)。

参考代码

CPP
#include <bits/stdc++.h>
using namespace std;

int logn, n, a[200024], fa[200024], d[200024], ls[200024], rs[200024], root, dep[200024], nfa[200024][20];
vector<int> G[200024];

int merge(int x, int y) {
    if (!x || !y) return x + y;
    if (a[x] > a[y]) swap(x, y);
    rs[x] = merge(rs[x], y);
    if (d[rs[x]] > d[ls[x]]) swap(ls[x], rs[x]);
    d[x] = d[rs[x]] + 1;
    return x;
}

int dfs(int u, int f) {
    d[u] = 1;
    fa[u] = 0;
    int prt = 0;
    for (auto v : G[u]) {
        if (v == f) continue;
        dep[v] = dep[u] + 1;
        nfa[v][0] = u;
        int tmp = dfs(v, u);
        int lst = 0;
        while (tmp && a[tmp] < a[u]) {
            if (lst) fa[lst] = tmp;
            lst = tmp;
            tmp = merge(ls[tmp], rs[tmp]);
        }
        if (lst) fa[lst] = u;
        prt = merge(prt, tmp);
    }
    fa[u] = prt;
    return merge(u, prt);
}

int lca(int u, int v) {
    if (dep[u] < dep[v]) swap(u, v);
    for (int i = logn; i >= 0; i--) if ((dep[u] - dep[v]) & (1 << i)) {
        u = nfa[u][i];
    }
    if (u == v) return u;
    for (int i = logn; i >= 0; i--) if (nfa[u][i] != nfa[v][i]) {
        u = nfa[u][i];
        v = nfa[v][i];
    }
    return nfa[u][0];
}

int dist(int u, int v) {
    int g = lca(u, v);
    return dep[u] + dep[v] - (dep[g] << 1);
}

long long dfsr2(int u, int f) {
    long long xans = 0;
    for (auto v : G[u]) {
        long long tmp = dfsr2(v, u) + dist(u, v);
        if (tmp > xans) xans = tmp;
    }
    return xans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if (a[i] == n) root = i;
    }
    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        G[u].push_back(v);
        G[v].push_back(u);
    }
    int x = dfs(root, -1), lst = 0;
    while (x) {
        if (lst) fa[lst] = x;
        lst = x;
        x = merge(ls[x], rs[x]);
    }
    for (int i = 1; i <= n; i++) G[i].clear();
    for (int i = 1; i <= n; i++) if (fa[i]) {
        G[fa[i]].push_back(i);
    }
    logn = __lg(n);
    for (int i = 1; i <= logn; i++) for (int j = 1; j <= n; j++) {
        nfa[j][i] = nfa[nfa[j][i - 1]][i - 1];
    }
    cout << dfsr2(root, -1) << '\n';
    return 0;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...