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

题目链接

• 洛谷 P9352 [JOI 2023 Final] 训猫 / Cat Exercise

题意简述

一棵树上有 $n$ 个权值不同的点，一开始有一只猫位于树上权值最大的点上。

每次可以选择在一个点上放置障碍，如果猫所在的点被放置障碍，则它会沿简单路径移动到能到达的点中权值最大的一个点上。

求能达成的猫的最大移动距离和。

解题思路

给出一个不太一样的思路。

考虑到因为给出的是一棵树，因此一旦离开某个点，就不可能到达与该点相连的其他点。

基于这一性质，实际上每次移动都会将猫的移动范围限制在上一个点的某棵子树内。

考虑进行搜索，传递状态为 $u$，搜索以 $u$ 为根的子树内，从该子树内权值最大的点开始能达到的最长移动距离和。

对于权值最大点的子树，这是好做的，我们只需要将结果取最大值即可。

设 $v$ 表示以点 $u$ 为根的子树内权值最大的点，于是我们就要考虑如何处理在以 $u$ 为根的子树内而在以 $v$ 为根的子树外的点。

直接做显然不好做，但是因为以 $v$ 为根的子树的内容不会影响到别的子树的结果。

所以我们可以在计算完以 $v$ 为根的子树之后直接将这一子树删去，然后再对剩余部分直接计算贡献，可以发现实际上就是在计算在以 $u$ 为根的子树内而在以 $v$ 为根的子树外的点的贡献。

只需要用线段树维护 dfn 进行删点（将权值更改为 $0$）和查询区间最大值操作即可。

复杂度为 $O(n\log n)$

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll N = 200005;
ll n , h[N] , fa[N] , dfn[N] , pos[N] , dfncnt = 0;
ll top[N] , dep[N] , siz[N] , son[N];
bool del[N];
vector <ll> g[N];

struct seg {ll l , r , mx , tag;} s[N << 2];

void dfs(ll u , ll f)
{
    fa[u] = f; siz[u] = 1; dep[u] = dep[f] + 1;
    pos[dfn[u] = ++dfncnt] = u;
    for(auto v : g[u]) if(v != f)
        dfs(v , u) , siz[u] += siz[v],
        son[u] = (siz[son[u]] < siz[v] ? v : son[u]);
}

void dfs2(ll u)
{
    if(!son[u]) return;
    top[son[u]] = top[u];
    dfs2(son[u]);
    for(auto v : g[u]) if(v != fa[u] && v != son[u])
        top[v] = v , dfs2(v);
}

ll lca(ll u , ll v)
{
    while(top[u] != top[v])
    {
        if(dep[top[u]] < dep[top[v]]) swap(u , v);
        u = fa[top[u]];
    }
    return dep[u] < dep[v] ? u : v;
}

ll dis(ll u , ll v) {return dep[u] + dep[v] - 2 * dep[lca(u , v)];}

void build(ll id , ll l , ll r)
{
    s[id].l = l; s[id].r = r;
    if(l == r) {s[id].mx = pos[l]; return;}
    ll mid = (l + r) >> 1;
    build(id << 1 , l , mid); build(id << 1 | 1 , mid + 1 , r);
    s[id].mx = h[s[id << 1].mx] > h[s[id << 1 | 1].mx] ? s[id << 1].mx : s[id << 1 | 1].mx;
}

void pushdown(ll id)
{
    if(s[id].tag)
    {
        s[id << 1].tag = 1; s[id << 1].mx = 0;
        s[id << 1 | 1].tag = 1; s[id << 1 | 1].mx = 0;
        s[id].tag = 0;
    }
}

void update(ll id , ll l , ll r)
{
    if(s[id].l > r || s[id].r < l || s[id].tag) return;
    if(s[id].l >= l && s[id].r <= r) {s[id].tag = 1; s[id].mx = 0; return;}
    pushdown(id);
    update(id << 1 , l , r); update(id << 1 | 1 , l , r);
    s[id].mx = h[s[id << 1].mx] > h[s[id << 1 | 1].mx] ? s[id << 1].mx : s[id << 1 | 1].mx;
}

ll query(ll id , ll l , ll r)
{
    if(s[id].l > r || s[id].r < l || s[id].tag) return 0;
    if(s[id].l >= l && s[id].r <= r) return s[id].mx;
    ll la = query(id << 1 , l , r) , ra = query(id << 1 | 1 , l , r);
    return h[la] > h[ra] ? la : ra;
}

ll find_ans(ll u)
{
    ll v = query(1 , dfn[u] , dfn[u] + siz[u] - 1) , res = 0;
    if(!v) return 0;
    for(auto w : g[v])
        if(w != fa[v] && !del[w])
        {
            ll tmp = dis(v , query(1 , dfn[w] , dfn[w] + siz[w] - 1));
            res = max(res , find_ans(w) + tmp);
        }
    update(1 , dfn[v] , dfn[v] + siz[v] - 1); del[v] = 1;
    if(u != v)
    {
        ll tmp = dis(query(1 , dfn[u] , dfn[u] + siz[u] - 1) , v);
        res = max(res , find_ans(u) + tmp);
    }
    return res;
}

signed main()
{
    freopen(".in" , "r" , stdin);
    freopen(".out" , "w" , stdout);
    cin >> n;
    for(ll i = 1 ; i <= n ; i++) cin >> h[i];
    for(ll i = 1 , u , v ; i < n ; i++)
        cin >> u >> v , g[u].push_back(v) , g[v].push_back(u);
    dfs(1 , 0); top[1] = 1; dfs2(1); build(1 , 1 , n);
    cout << find_ans(1) << '\n';
    return 0;
}