题解：P17851 「RiOI-(-2)」houran 和芒果 / [ROI 2026 Day1] 泰莫利亚的调查 加强版

· · 题解

题意是将以 1 为根的树剖分出 m 条不交的树链，求树链权值和的最大值。

先看一个弱化版，选 m 条树链求树链覆盖点权和的最大值（Luogu P10641）。考虑一个显然的贪心，设 d_u 表示根到 u 的点权和，每次选择 d_u 最大的点并将链上所有边的边权改为 0。可以用数据结构做到 O(n\log n)。但实际上，我们可以考虑类似长剖的方式，每次选择最长的长链，可以做到 O(n)。

为什么是对的？一个以 u 为根的长链一定比以 son_{fa_u} 为根的长链更短，也就是后者一定更优。

回到本题，考虑将原问题转化。对于点 u 最优的情况肯定是选择一个边权最大且子树内有选择点的儿子 v。那么首先对每个点儿子的边权升序排序，考虑类似差分的结构（如下图）：

例如当 v(4) 被选时，4\to u 的所有边都会被计算，此时的总权值就是 w(4)，可以恰好凑出最大的一位的权值。于是对于每一个节点建出上图结构后做前面提到的树链覆盖最大权即可，时间复杂度 O(Tn)。

由于需要大量复杂卡常，这里给出可读性高的未卡常代码。

:::success[Code]

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 4e5 + 5 , V = 1 << 18;
vector <int> c[V] , g[N] , G[N];
int n , k , x[4] , fa[N] , d[N] , W[N] , w[N] , son[N] , S[N] , idx;
int cnt[V] , tmp[N];
void Dfs (int u)
{
    son[u] = 0;
    for (int v : G[u])
    {
        Dfs (v);
        if (d[son[u]] <= d[v]) son[u] = v;
    }
    for (int v : G[u]) if (v != son[u])
        S[++ idx] = d[v];
    d[u] = d[son[u]] + w[u];
}
signed main ()
{
    ios::sync_with_stdio (0);
    cin.tie (0) , cout.tie (0);
    cin >> n;
    for (int i = 2;i <= n;i ++) cin >> fa[i];
    for (int i = 2;i <= n;i ++) cin >> W[i];
    int T;
    cin >> T;
    while (T --)
    {
        cin >> x[0] >> x[1] >> x[2] >> x[3] >> k;
        for (int i = 0;i < V;i ++) c[i].clear ();
        for (int i = 1;i <= n;i ++) g[i].clear ();
        for (int i = 1;i <= (n << 1);i ++) G[i].clear () , d[i] = 0;
        for (int i = 2;i <= n;i ++) w[i] = W[i] ^ x[i & 3] , c[w[i]].push_back (i);
        for (int i = 0;i < V;i ++)
            for (int v : c[i])
                g[fa[v]].push_back (v);
        int cc = n;
        for (int i = 1;i <= n;i ++)
        {
            int lst = i , lstw = 0;
            for (int v : g[i])
            {
                cc ++;
                G[lst].push_back (cc);
                G[cc].push_back (v);
                w[cc] = w[v] - lstw;
                lstw = w[v] , lst = cc;
                w[v] = 0;
            }
        }
        idx = 0;
        Dfs (1);
        S[++ idx] = d[1];
        nth_element (S + 1 , S + idx - k , S + idx + 1);
        int ans = 0;
        k = min (k , idx);
        for (int i = idx - k + 1;i <= idx;i ++) ans += S[i];
        cout << ans << '\n';
    }
    return 0;
}

:::