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

· · 题解

考虑延迟钦定 dp：子树合并记录当前 \text{mex} 以及剩余待定点数，在这个点增加 \text{mex} 需要使用待定点数。直接做是 \mathcal O(n^4)，由树上背包复杂度分析以及前缀 \max 优化，时间复杂度 \mathcal O(n^3)。

上述做法二三维基于子树大小，但是题中限制是深度。考虑将继承 \text{mex} 的儿子标出来，这样别的子树向上的贡献就只有内部剩余的点数。发现这是链剖分的结构，此时考虑每个点的贡献，从它往上跳会有若干段重链，那么发现它的贡献就是最长一段重链的点数。容易想到记录上面的信息，状态是 f_{u,i,j} 表示 u 子树上面最长是 i 且 u 是所在重链第 j 个，子树内部的最大贡献。转移钦定一个 f_{v,i,j+1} 以及别的 f_{v,\max(i,j),1}，这样是 \mathcal O(nm^2)。注意到 i-j>height_u 时一定子树内所有点都选 i，这样 u 的状态数是 \mathcal O(mh_u)。直接长链剖分优化，根据短链范围总和是 \mathcal O(n)，对继承短儿子暴力，继承长儿子用手法优化即可 \mathcal O(nm)。太难写了。

从状态的角度优化，i,j 同时记录是很没必要的。考虑只记录 i，这样状态为 f_{u,i} 表示 u 为 fa_u 的轻儿子，且上面贡献为 i 时，子树内部最大贡献。考虑直接枚举子树内某个叶子 v 作为 u 开头的重链链底来求 f。u\to v 重链上所有点贡献就容易算，瓶颈在于转移轻子树的贡献，观察 f(x)=\max(\text{dist}(x,u),i)，形如前缀被 i 抬升后接上斜线。后面斜线是与 i 无关的，而前面所有 f(x) 都是确定的 i。一种写法是，将点权设置为所有儿子的贡献和减去这个点的贡献和，就转化为直接求和（重链的被容斥掉）。

在树上从 u 向下进行 dfs，容易求出 \text{dist}(x,u)>i 部分的贡献，具体可以容斥为两段前缀之差；考虑 \text{dist}(x,u)\leq i，形如单点修改与直链查询，求 dfs 序后树状数组维护即可。具体实现上可以自由钦定拐点位置，时间复杂度 \mathcal O(nm\log n)。

#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define uint unsigned
#define pb push_back
#define mkp make_pair
#define fi first
#define se second
#define inf 1000000000
#define infll 1000000000000000000ll
#define pii pair<int,int>
#define rep(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define per(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define dF(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define eb emplace_back
#define SZ(x) ((int)x.size())
#define all(x) x.begin(),x.end()
using namespace std;
bool ST;
void fre(){
    // freopen("tree.in","r",stdin),freopen("tree.out","w",stdout);
}
inline int lowbit(int x){ return x&(-x); }
template<typename T>inline void chkmax(T &x,const T &y){ x=std::max(x,y); }
template<typename T>inline void chkmin(T &x,const T &y){ x=std::min(x,y); }
const int mod=998244353,maxn=8005,MR=805;
vector<int>g[maxn];
int n,m,fa[maxn];
struct BIT{
    int t[maxn];
    void init(){ memset(t,0,sizeof t); }
    void add(int l,int r,int val){
        if(l>r)return;
        for(;l<=n;l+=lowbit(l))t[l]+=val;
        for(++r;r<=n;r+=lowbit(r))t[r]-=val;
    }
    int qry(int x){
        int res=0;
        for(;x;x&=(x-1))res+=t[x];
        return res;
    }
}tr[MR];
int dfn[maxn],rev[maxn],tim,siz[maxn],ed[maxn],dep[maxn];
void dfs0(int u){
    rev[dfn[u]=++tim]=u,siz[u]=1,dep[u]=dep[fa[u]]+1;
    for(int&v:g[u])dfs0(v),siz[u]+=siz[v];
    ed[u]=tim;
}
int f[maxn][MR],h[maxn][MR],sum[MR];
void solve(){
    cin>>n>>m,++m,tim=0;
    F(i,0,m)tr[i].init();
    F(u,1,n)F(i,0,m)f[u][i]=h[u][i]=0;
    F(i,1,n)g[i].clear();
    F(i,2,n)cin>>fa[i],g[fa[i]].push_back(i);
    dfs0(1);
    dF(u,n,1){
        F(i,0,m)sum[i]=0;
        F(i,1,dep[u])f[u][i]=i*siz[u];
        for(int&v:g[u])F(i,0,dep[u])sum[i]+=f[v][i];
        F(i,1,dep[u])for(int&v:g[u])tr[i].add(dfn[v],ed[v],i+sum[i]-f[v][i]);
        for(int&v:g[u])F(i,0,dep[u])chkmax(h[u][i],h[v][i+1]+sum[i]-f[v][i]);
        F(i,1,dep[u])h[u][i]+=i;
        F(i,dfn[u],ed[u]){
            const int x=rev[i],d=dep[x]-dep[u]+1;
            if(d<=dep[u])chkmax(f[u][d],h[x][d]+tr[d].qry(dfn[x]));
        }
        chkmax(f[u][0],h[u][1]);
    }
    cout<<f[1][0]<<'\n';
}
bool ED;
signed main(){
    fre(),ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int wzq=1;cin>>wzq;
    F(____,1,wzq)solve();
    cerr<<"time used: "<<(double)clock()/CLOCKS_PER_SEC<<endl;
    cerr<<"memory used: "<<abs(&ST-&ED)/1024.0/1024.0<<" MB"<<endl;
}
// g++ P14637.cpp -o a -std=c++14 -O2