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

· · 题解

假装这是验题人题解。

反悔贪心做法。

如果要求是边不相交就是直接长剖选叶子，但本题要求点不相交。在一个子树允许的叶子数上升的时候，这个子树的根节点往下会改连更大的边。

考虑 dp_{i,j} 表示以 i 为根的子树，允许选 j 个叶子的答案。差分一下，改成表示能选第 j 个叶子时答案的增加量。显然值随 j 不增。

大概思路是，u 合并子树时，u 向下连的边改变的影响是让一个子树第一次被选的贡献增加 w_v，撤回上个第一次被选子树的 w_v。在 dp 数组上体现为 dp_{v,1} 的贡献加上 w_v-w_{lst}。而 dp 数组 j>1 的部分直接继承，因为这个子树选完第一次后随时可以在里面多选。

算法流程：

  1. 对于 dp_{v,1}，把所有子树按照 dp_{v,1}+w_v 从大到小排序，取值最大的 v' 更新 dp_{u,1}=dp_{v',1}+w_{v1}。
  2. 令 lst=v'，然后按上面顺序遍历 v \neq v'。如果 w_v<w_{lst}，则把 dp_{v,1}+w_{lst}-w_v 加入额外数组 y，且更新 lst=v；否则把 dp_{v,1} 原样加入数组 y。
  3. 把所有 dp_{v,j} (j>1) 加入数组 y。
  4. 把 y 从大到小排序，作为 dp_{u,2\sim叶子个数}。

正确性：

  1. 对于每个 v 子树，只有 dp_{v,1} 的贡献上升，所以在 dp_u 中的相对位置不变，能以子树内原本顺序合法选择。
  2. 对于每个 dp_{v,1}，根据排序方法显然答案达到上界。

直接用 set 启发式合并，特殊处理 dp_{v,1}，最后前缀和完输出第 m 个元素，可做 O(n\log^2 n)。

代码较丑，就不放了。

发现这太唐了，dp_{v,2\sim叶子个数} 这部分一直在合并但从来没有改过。所以把上面第 2,3 步中的 y 数组改成全局的，最后统一排序，可以做到 O(n\log n)。

:::info[代码]

#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
const int N=210000;
int t,n,d1[N],fa[N],w1[N],w[N],X[4],k,tot;
long long x[N],y[N];
vector<int>e[N];
bool cmp1(int a,int b){
    return w[a]+x[a]>w[b]+x[b];
}
inline void dfs0(int u){
    d1[++tot]=u;
    for(int v:e[u])dfs0(v);
}
bool cmp(long long x,long long y){
    return x>y;
}
inline void read(int&x){
    char c=getchar();
    while(!('0'<=c&&c<='9'))c=getchar();
    x=0;
    while('0'<=c&&c<='9')x=x*10+c-'0',c=getchar();
}
int main(){
    //freopen("mango.in","r",stdin);
    //freopen("mango.out","w",stdout);
    read(n);
    for(int i=2;i<=n;i++)read(fa[i]),e[fa[i]].push_back(i);
    for(int i=2;i<=n;i++)read(w1[i]);
    dfs0(1);
    read(t);
    while(t--){
        for(int i=0;i<4;i++)read(X[i]);
        read(k);
        for(int i=2;i<=n;i++)w[i]=w1[i]^X[i%4];
        tot=0;
        for(int i=n;i>=1;i--){
            int u=d1[i];
            x[u]=0;
            if(e[u].empty())continue;
            sort(e[u].begin(),e[u].end(),cmp1);
            int v1=e[u][0];
            x[u]=x[v1]+w[v1];
            for(int v:e[u]){
                if(v==v1)continue;
                y[++tot]=x[v]+max(w[v]-w[v1],0);
                if(w[v]>w[v1])v1=v;
            }
        }
        y[++tot]=x[1];
        sort(y+1,y+tot+1,cmp);
        //for(int i=1;i<=tot;i++)cout<<y[i]<<' ';
        //cout<<endl;
        for(int i=1;i<=tot;i++)y[i]+=y[i-1];
        printf("%lld\n",y[min(k,tot)]);
    }
    return 0;
}

:::

考虑继续优化到线性。这时瓶颈是两个 sort。

对于 dfs 中对所有儿子的排序，值域大不好优化。但注意到我们在做的事形如一维 dp_{v,1}+w_v 一维 w_v 的最长上升子序列状物。考虑换维，变成按 w_v 从大到小排序，修改 dp_{v,1} 在 y 中的 w_{lst}-w_v 状贡献。这样值域就是 2^{17} 的了，可以对所有边统一进行一次计数排序。

对于最外面的排序，注意到我们是先把 y 排序后取前缀和第 m 项。改成对 y 数组 nth_element() 后前 m 项和即可线性。

为卡掉 1\log，常数要求较大，但写法好一般没有太大问题。

我的实现没有这么优秀，荣获最劣解（

:::info[代码]

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=210000;
int t,n,d1[N],fa[N],w1[N],w[N],X[4],k,tot;
long long x[N],y[N],ans;
int m,cnt[N],rk[N],at[N],e1[N],le[N],re[N];
basic_string<int>e[N];
bool cmp1(int a,int b){
    return w[a]+x[a]>w[b]+x[b];
}
inline void dfs0(int u){
    d1[++tot]=u;
    for(int v:e[u])dfs0(v);
}
bool cmp(long long x,long long y){
    return x>y;
}
inline void read(int&x){
    char c=getchar();
    while(!('0'<=c&&c<='9'))c=getchar();
    x=0;
    while('0'<=c&&c<='9')x=x*10+c-'0',c=getchar();
}
int main(){
    //freopen("mango8.in","r",stdin);
    //freopen("mango.out","w",stdout);
    read(n);
    for(int i=2;i<=n;i++)read(fa[i]),e[fa[i]].push_back(i);
    for(int i=1;i<=n;i++)le[i]=re[i-1]+1,re[i]=le[i]+e[i].size()-1;
    for(int i=2;i<=n;i++)read(w1[i]);
    dfs0(1);
    read(t);
    while(t--){
        for(int i=0;i<4;i++)read(X[i]);
        read(k);
        for(int i=2;i<=n;i++)w[i]=w1[i]^X[i%4];
        m=0;
        for(int i=2;i<=n;i++)m=max(m,w[i]);
        for(int i=0;i<=m;i++)cnt[i]=0;
        for(int i=2;i<=n;i++)cnt[w[i]]++;
        for(int i=m-1;i>=0;i--)cnt[i]+=cnt[i+1];
        for(int i=2;i<=n;i++)rk[cnt[w[i]]--]=i;
        for(int i=1;i<=n;i++)re[i]=le[i]-1;
        for(int i=1;i<n;i++)e1[++re[fa[rk[i]]]]=rk[i];
        tot=0;
        for(int i=n;i>=1;i--){
            int u=d1[i];
            x[u]=0;
            if(le[u]>re[u])continue;
            int v1=0;
            for(int i=le[u];i<=re[u];i++){
                int v=e1[i];
                if(x[v]+w[v]>x[v1]+w[v1])v1=v;
            }
            x[u]=x[v1]+w[v1];
            int lst=0;
            bool bol=0;
            for(int i=le[u];i<=re[u];i++){
                int v=e1[i];
                if(v==v1){bol=1;continue;}
                if(bol||w[v]+x[v]<=w[lst]+x[lst])y[++tot]=x[v],at[v]=tot;
                else{
                    y[at[lst]]-=w[v];
                    y[++tot]=x[v]+w[v],at[v]=tot;
                    lst=v;
                }
            }
            y[at[lst]]-=w[v1];
        }
        y[++tot]=x[1];
        //for(int i=1;i<=tot;i++)cout<<y[i]<<' ';
        //cout<<endl;
        nth_element(y+1,y+min(k,tot),y+tot+1,cmp);
        ans=0;
        for(int i=1;i<=tot&&i<=k;i++)ans+=y[i];
        printf("%lld\n",ans);
    }
    return 0;
}

:::

另外，场下这题还有一个类似的更本质的理解。把一个节点的每个儿子按照 w 从大到小排序，二度化，原儿子顺序连接，边权为 w_v 之差。本质上是对反悔贪心的过程显式地建树。在新树上，本题被转化为边不交的问题，正常长剖即可线性，写出来其实一摸一样。

所以怎么真的有一万种做法写出来是一个东西