题解：P14637 [NOIP2025] 树的价值 / tree（官方数据）

· · 题解

纪念第一个全调完的 CCF 系列赛事。

第一眼看过去，发现明显部分分分成三部分，考虑第一部分 n\le 360 应当是平凡的。

我们考虑到一个节点为根的子树中所有节点 a 的值肯定是包含其所有儿子子树的。

那么这个子树的 \mathrm{mex} 必然比其所有儿子子树的都大或相等。

考虑一个假贪心就是每次一个节点填的数使得这个子树恰好相对最大的儿子垫高一。

不过我们并不认为它很有道理，而且注意到数据范围，所以不对。

我们考虑如果不是这样，那么这个子树就会和最大的那个儿子的 \mathrm{mex} 相等，那么需要在更大子树产生别的贡献。

考虑可以这里填的大一些，在某个祖先处使得祖先变大 1，到这个祖先后就没用了。

于是设 dp_{i,j,k} 表示以 i 为根的子树中，i 子树的 \mathrm{mex} 为 j，并且有 k 个节点没用，打算在祖先使用。

转移就是枚举 i，然后每个 i 枚举 j，接着随便算一下，然后看一下用几个 k 即可。

这样实现优秀就是 48 分。

但是这样细节不是特别少，而且分数不高，而且题目给的 m 没用到，显然并不会让人甘心。

于是考虑刻画这个东西。

我们发现根在使用没用的节点之前，\mathrm{mex} 必然从某个儿子转移，我们说这个儿子是他的嫡长子（借用某同学起的名），这条边叫做他的继承边。

我们考虑一个没用的节点在当前使用会发生什么。

此时我们发现从这里往上一直走继承边的节点都会被贡献，但如果某次走的不是继承边，之后不被贡献。

我们到这里发现可以贪心一部分，就是一个节点只给他到根节点中最长的连续嫡长子的底部进行贡献，产生链长的贡献。

我们考虑 DP 过程钦定嫡长子来计算答案。

设 dp_{i,j,k} 表示 i 为根的子树，i 节点是当前嫡长子链的第 j 个节点，i 到根最长嫡长子链长度为 k。

发现非常好转移，还是枚举 i，然后枚举嫡长子，最后加上自己贡献就行。

复杂度 O(nm^2)。

获得 76 分，赛场上这个分数足以让你剩下时间安心攻 T4。

考虑怎么优化，其实我们第二维可以去掉，然后设当前节点为当前嫡长子连最顶端，枚举当前链到哪个叶子暴力转移。

考虑稍微聪明点，设 f_{i,j} 表示 i 子树并且当前嫡长子链和最长嫡长子链长度相等，长度为 j 的最大价值。

然后我们考虑 f 容易转移。

但是 dp_{i,j} 转移变成链端点只需要找到一个链长为 j 的位置，从那里 f 转移过来，链上贡献为 j，别的子树的 dp_{v,j} 即可。

复杂度还是假的。

设 w_{i,j} 表示只考虑考虑当前的根子树链到 i 这条链上所有被分开子树的贡献，并且我们这里链长为 j。

于是每次根往上走就是对每个 j 的 w_{i,j} 子树加，暴力转移即可。

复杂度就是子树大小之和乘 \log 等于祖先大小之和乘 \log 等于 O(nm\log n)。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int dp[8009][809];
int f[8009][809];
vector<int> s[8009];
int dep[8009];
int ped[8009];
int sz[8009];
int pd[8009][809];
int fa[8009];
int dfn[8009];//point i's bianhao
int rr[8009];//bianhao's r
int inn;
struct szsz{
    int f[8009];
    int lowbit(int t){
        return t&(-t);
    }
    void op(int t,int k){
        while(t<=8001){
            f[t]+=k;
            t+=lowbit(t);
        }
    }
    int query(int t){
        int ans;
        ans=0;
        while(t){
            ans+=f[t];
            t-=lowbit(t);
        }
        return ans;
    }
    void pls(int l,int r,int k){
        op(l,k),op(r+1,-k);
    }
}w[809];
void fs(int t){
    int cc;
    cc=inn+1;
    dfn[t]=++inn;
    for(auto v:s[t]){
        fs(v);
    }
    rr[cc]=inn;
}
void zy(int t,int rt){
    if(dep[t]-dep[rt]+1>dep[t]){
        return; 
    }
    for(auto v:s[t]){
        zy(v,rt);
    }

    dp[rt][dep[t]-dep[rt]+1]=max(dp[rt][dep[t]-dep[rt]+1],w[dep[t]-dep[rt]+1].query(dfn[t])+(dep[t]-dep[rt])*(dep[t]-dep[rt]+1));
}
void dfs(int t){
    ped[t]=1;
    sz[t]=1;
    for(auto v:s[t]){
        dfs(v);
        ped[t]=max(ped[t],ped[v]+1);
        sz[t]+=sz[v];
    }for(int ma=1;ma<=dep[t]+1;ma++){
        for(auto v:s[t]){
            pd[t][ma]+=dp[v][ma];
        }
    }
    for(int ma=1;ma<=dep[t];ma++){
        int sum;
        sum=0;
        for(auto v:s[t])
            sum+=dp[v][ma];
        for(auto v:s[t])
            f[t][ma]=max(f[t][ma],sum-dp[v][ma]+f[v][ma+1]);
        f[t][ma]+=ma;
        w[ma].pls(dfn[t],dfn[t],f[t][ma]);
    }
    dp[t][1]=f[t][1];
    for(int i=1;i<=dep[t]+1;i++){
        int cc=0;
        for(auto v:s[t]){
            cc+=dp[v][i];
        }
        for(auto v:s[t]){
            cc-=dp[v][i];
            w[i].pls(dfn[v],rr[dfn[v]],cc);
            cc+=dp[v][i];
        }
    }
    zy(t,t);
    for(int ma=ped[t];ma<=dep[t];ma++){
        dp[t][ma]=sz[t]*ma;
    }
}
void _main(){
    int n,m;
    cin>>n>>m;
    inn=0;
    for(int i=1;i<=n;i++){
        s[i].clear();
    }
    memset(dp,0,sizeof(dp));
    memset(pd,0,sizeof(pd));
    memset(f,0,sizeof(f));
    memset(w,0,sizeof(w));
    dep[1]=1;
    for(int i=2;i<=n;i++){
        int faa;
        cin>>faa;
        dep[i]=dep[faa]+1; 
        fa[i]=faa;
        s[faa].push_back(i);
    }
    fs(1);
    dfs(1);
    cout<<dp[1][1]<<endl;
}
signed main(){
    //freopen("tree.in","r",stdin);
    //freopen("tree.out","w",stdout);
    std::ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        _main();
    }
    return 0;
}