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

· · 题解

题意

给定一颗有大小 n 的根树，边有边权。

给定 m，你选择至多 m 条树上的简单路径，并且每条路径的两个端点有祖先关系，这些路径点集不交，求所有路径边权和的和的最大值。

要求关于边权和 n 做到线性。

题解

相当巧妙啊。

考虑费用流建模，每个点拆成两个点，容量是 1，接着边是费用，最后可以建立出费用流模型。

因此答案关于 m 是凸的，每个子树也是这样的。

考虑设 dp_{i,j} 表示 i 子树操作 j 次得到最大价值。

我们枚举 w_v 最大的儿子，然后对前面做闵可夫斯基和，精细实现后复杂度是 O(nm)。

我们考虑为什么暂时做不了 O(n\log^2 n)。

因为我们不知道当前选择哪个儿子的 w_v。

我们回想一般的闵可夫斯基和，就是 dp_i 作差，得到若干个元素，把这些元素合到一起排序，可以启发式合并堆做到两只 \log 或者一只。

我们从考虑在有边权的时候相当于对最终堆的某些元素增加了一个数，这个数是某两个边权的差并且不小于 0。

而且考虑某个元素原先的归属，从大到小添加元素的时候，如果这个元素属于新的子树并且其对应儿子边权更大， 那么就会增加儿子边权和之前最大儿子边权的差。

我们只关心每个子树第一个元素，这些才会影响增加量。这个容易计算每个点 dp_{i,1}。

设 g_i=dp_{i,1}，考虑所有 g_v+w_v，如果某次加入后某个人 w_v 是最大的，那么要求没有 w_v+g_v 比他大的没选，否则可以调整。

如果一个东西的 w_v+g_v 和 w_v 都比某个人小，那么他的 w_v 永远不可能是最大的，于是把它的 w_v 变成 0，扔出考虑范围。

剩下的容易看出选 i 个就是选择 w_v+g_v 最大的 i 个，按照 w_v 从小到大排序之后就是选择前缀，那么每次添加的增加量就是 g_i+w_i-w_{i-1}。

于是我们把 w_i 改成 w_i-w_{i-1} 或者被扔出去的就是 0。

然后就是每个子树的所有 dp_{v,j} 增加 w_v 之后合并。

可以闵可夫斯基做到 O(n\log^2 n) 或者 O(n\log n)。

考虑优化。

我们发现其可以刻画成每次选择一条路径，要求每次路径的边不交，选择的路径端点有祖先关系，求 m 次选择最大边权和。

我们这时候可以直接模拟贪心，还是 O(n\log n)，但是好写很多。

考虑刻画贪心过程，我们发现就是我们每次选择一个点到它子树内叶子的路径，并且在走的过程中，除了第一次以外，之后都会贪心选择。

具体而言，考虑从 i 往子孙走能走最大的权值是 c_i。

某一次选择的上端点是 t，因为 t 的一些边被选择了，所以第一次选择哪个边都可能。

记选择的是 s，我们发现此时 s 必然是第一次被选择，否则这条边不可能被空出来。

于是之后走的就是 s 儿子中 c_v 最大的。

进一步的，我们思考每次一个点 t 贪心选择最大的 c_v，除了根之外，这条路径必然会被 t 的父亲走过，它并没有机会。

如果某次选择的不是最大的 c_v，则其作为上端点必然是对的，因为其父亲已经在最大的 c_v 用过。

于是我们发现我们最终走哪些路径是已经确定的，线性得到这些路径的权值，放入数组，转化为求数组前 m 大值。可以期望线性做。

复杂度瓶颈变成了前面的对儿子的 w 排序。

考虑整体的 w 做一遍桶排序，然后从小到大加入儿子即可。

时间复杂度 O(T(n+V))。

值得注意的是，由于它是多次询问，所以基排复杂度是错的，基排复杂度是 O(TN)，其中 N 是初始输入量。但是之后因为特殊的输入方式，每次都做输入量复杂度其实并不能接受。

#include<bits/stdc++.h>
using namespace std;
//#define int long long
const int V=(1<<17);
int fa[200009];
int www[200009];
int w[200009];
int n;
long long dp[200009];
bool cmp1(int x,int y){
    return w[x]<w[y];
}
long long a[200009];
int inn;
int gg[V+9];
int p[200009];
int am[200009];
void _main(){
    int m;
    cin>>m;
    memset(gg,0,sizeof(gg));
    memset(dp,0,sizeof(dp));
    memset(am,-1,sizeof(am));
    for(int i=n;i>=2;i--){
        dp[fa[i]]=max(dp[fa[i]],dp[i]+w[i]);
        gg[w[i]]++;
    }
    for(int i=1;i<V;i++){
        gg[i]+=gg[i-1];
    }
    for(int i=2;i<=n;i++){
        p[(gg[w[i]]--)]=i;
    }
    for(int i=n-1;i>=1;i--){
        int v;
        v=p[i];
        int t;
        t=fa[v];
        int ma;
        ma=am[t];
        if(ma==-1||w[v]+dp[v]>w[ma]+dp[ma]){
            if(ma!=-1){
                w[ma]-=w[v];
            }
            am[t]=v;
        }else{
            w[v]=0;
        }
    }
    inn=0;
    memset(dp,0,sizeof(dp));
    memset(am,-1,sizeof(am));
    for(int i=n;i>1;i--){
        int t;
        t=fa[i];
        int ma;
        ma=am[t];
        if(ma==-1||w[i]+dp[i]>w[ma]+dp[ma]){
            am[t]=i;
            dp[t]=w[i]+dp[i];
        }
    }
    for(int i=n;i>1;i--){
        if(i!=am[fa[i]]){
            a[++inn]=w[i]+dp[i];
        }
    }
    a[++inn]=dp[1];
    m=min(m,inn);
    nth_element(a+1,a+1+m,a+1+inn,greater<long long>());
    long long ans;
    ans=0;
    for(int i=1;i<=m;i++){
        ans+=a[i];
    }
    cout<<ans<<"\n";
}
signed main(){
    std::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>>www[i];
    }
    int t;
    cin>>t;
    while(t--){
        int x[4];
        cin>>x[0]>>x[1]>>x[2]>>x[3];
        for(int i=2;i<=n;i++){
            w[i]=(www[i]^x[i&3]);
        }
        _main();
    }
    return 0;
}