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

· · 题解

很牛的题。

我们要求的就是 m 条链覆盖，价值为链上边权和。显然最优解中所有链一定从叶子往上延伸。考虑 u 的儿子 v_1,v_2,\dots,v_t，点 u 能够选择一个子树内部有被选叶子的儿子接一条链，设内部有叶子的儿子构成集合 S，那么 u 带来的贡献就是 \max_{i\in S} w_i。现在问题转化成：

选择 m 个叶子，每个点带来的贡献是 \max_{i\in S_u} w_i，最大化贡献和。

我们发现这个 \max 不好处理。不妨先把 w 升序排序为 w_1\le w_2\le\dots \le w_t，这样如果钦定最大的有叶儿子为 i 则会造成 w_i 的贡献，同时限定只有 [1,i] 中的子树有叶子。考虑用差分转化，构造 t 个检测器，第 i 个检测器表示若 [i,t] 中存在子树有叶子，则造成 w_i-w_{i-1} 的贡献。假设最深的有叶儿子为 i，那么 \le i 的检测器都被触发，造成的贡献总和恰好为 w_i，与实际贡献吻合。不妨建立 t 个虚点表示这些决策，虚点 k_i 表示 [i,t] 中有儿子被选择。进行如下构造：令 k_i 向 k_{i+1} 和儿子 v_i 连边，为 k_i 设置点权 c_i=w_i-w_{i-1}。

在这棵新树上原本的边权覆盖转化成了点权覆盖。因此问题变成：

求 m 条链覆盖能够得到的点权和最大值。

这个就是经典问题了，有一个显然的贪心就是每次选择贡献最大的点，发现这个过程等价于按边权为权重进行长链剖分，然后取前 m 大的长链。你当然可以直接将树显式的建出来进行长链剖分。

但是进一步分析可以发现不用真的把虚点建出来，考虑向上合并时长链信息如何更新。令 d(u) 表示已经合并进点 u 的儿子往下延伸的链长。按 w 从大到小遍历儿子，转移形如：d(u)^\prime\leftarrow \max(d(v_i),d(u))+w_i-w_{i-1}。在转移过程中顺带把所有长链也找到了。

此题要求线性，因此不能对每个 u 都 sort 其儿子，直接在外面基数排序一次就行了。求答案涉及到前 m 小的和，用 nth_element 即可做到线性。因此总时间复杂度 O(T(n+\mathrm{RadixSort}(V)))。

upd：这个做法如果写的不好看是会被卡常的，注意不要用 vector 存每个点的儿子，改成按照 (\mathrm{fa}_u,w_u) 的双关键字基数排序，这样每个点的儿子体现在排序数组上就是一段连续区间。

:::success[代码]

#include <bits/stdc++.h>
#define psb push_back
#define lc (u<<1)
#define rc (u<<1|1)

using namespace std;

typedef long long ll;
template<class T>void Min(T &x,T y) { if (y<x) x=y; }
template<class T>void Max(T &x,T y) { if (y>x) x=y; }
const ll INF=1e18;
const int N=200010;
int n,m; int fa[N], w[N]; 
int cnt[N], id[N], ord[N]; ll buc[N]; int tot; 
int lson[N], rson[N]; ll d[N];

void work()
{
    for (int i=0;i<(1<<17);i++) cnt[i]=0;
    for (int i=2;i<=n;i++) cnt[w[i]]++;
    for (int i=1;i<(1<<17);i++) cnt[i]+=cnt[i-1];
    for (int i=n;i>=2;i--) id[cnt[w[i]]--]=i;
    memset(cnt,0,sizeof(int)*(n+1));
    for (int i=1;i<n;i++) cnt[fa[id[i]]]++;
    for (int i=2;i<=n;i++) cnt[i]+=cnt[i-1];
    for (int i=n-1;i;i--) ord[cnt[fa[id[i]]]--]=id[i];
    for (int i=1;i<=n;i++) lson[i]=n+1, rson[i]=0;
    for (int i=1;i<n;i++) Min(lson[fa[ord[i]]],i), Max(rson[fa[ord[i]]],i);

    tot=0; 
    for (int u=n;u;u--)
    {
        d[u]=0;
        for (int i=rson[u];i>=lson[u];i--)
        {
            int v=ord[i];
            ll delta=w[v]-(i>lson[u] ? w[ord[i-1]] : 0);
            if (d[v]>d[u]) swap(d[u], d[v]);
            d[u]+=delta; if (d[v]) buc[++tot]=d[v];
        }
    }
    buc[++tot]=d[1];
    m=min(m,tot); nth_element(buc+1,buc+m,buc+tot+1,greater<ll>());
    ll ans=0; for (int i=1;i<=m;i++) ans+=buc[i];
    cout << ans << "\n";
}

int main()
{
    ios::sync_with_stdio(false);
    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--)
    {
        int bse[4]; cin >> bse[0] >> bse[1] >> bse[2] >> bse[3] >> m;
        for (int i=2;i<=n;i++) w[i]=w[i]^bse[i&3]; 
        work();
        for (int i=2;i<=n;i++) w[i]=w[i]^bse[i&3]; 
    }

    return 0;
}

:::