精华推荐

洛谷P14637 [NOIP2025] 树的价值题解与碎碎念

司马只因锥 2026-6-10 15:51:52 36 浏览 2 点赞 1 收藏

#题解

前言

本文去掉代码全文共 4800 字。

这篇博客并非完全意义上的题解，主要是对我学习这道题的思路回顾与总结，基于以下两篇题解融合和补充（所以记号不是我原创的，我觉得尤其是第二篇题解定义的名词非常形象易懂直接抄了），以及一些碎碎念。

写了很多细节问题，都是我在学习这个题时思考过的，所以这篇文章非常长。

两篇神犇的题解：

20_200（下文称作“第一篇题解”）
tiger2005（下文称作“第二篇题解”）

因为我是蒟蒻，我已经尽量在让这篇题解启发式了qwq，所以对于“显而易见的结论”讲述的废话可能很多，请巨佬们多多批评指教。

由于文章太长，写作周期也长，精修困难。如有不解请敲在讨论区，我若看到一定会尽力修正表述。

部分记号表

记号	含义
$son_u$	$u$ 节点的子节点集
$subt_u$	$u$ 节点的子树点集
$fa(u)$	$u$ 节点的父节点
$\vert subt_u\vert$	$u$ 节点的子树点集大小

暴力

这部分会有两个复杂度的做法，但均为暴力及其优化，与正解关联不大。但能从中初步理解某些性质，个人感觉还是比较重要的。由于本人是蒟蒻，这个暴力对我来说也是个难点之一，本着彻底学透的想法，这部分也会很长，可选择跳过。

考虑一个非常劣的贪心：从下到上对每一层点按层分配数值，叶子结点是 $0$ ，其父节点是 $1$ ……不用我说也知道这东西没有分。

那么为什么是极劣的呢？我们发现在这个策略里每个点都对自身 $\text{mex}$ 有贡献，这使得大量节点没有对祖先进行贡献而被浪费，因此一个特殊点便十分显然：有一些点不对自己的 $\text{mex}$ 做贡献，而是留给祖先，这部分点我们称之为“垫脚石”。

垫脚石的严格定义：自身权值 $a_u$ 严格大于自身 $\text{mex}$ 的点。

因此根据这些特殊点设计状态，设 $dp[u][i][j]$ 为 $u$ 子树根节点 $\text{mex}$ 为 $i$ ，子树内有 $j$ 个垫脚石，即有 $j$ 个点满足 $a_v>a_u$ 。

两位神犇对于这一暴力是完全口胡的，然而蒟蒻如我连这个暴力都无法写好，因此也将讲解一下。

暴力树上背包 $O(n^4)$

根节点需要决策自身，所以先不着急考虑根节点以及使用垫脚石。

设临时数组 $dp\_v[i][j]$ 表示当前合并的所有子树的 $\text{mex}$ 为 $i$ ，有 $j$ 个垫脚石。

初始状态为空， $dp\_v[0][0]=0$ ，其余状态全部设置为极小值表示不可能。

合并的过程中，总 $\text{mex}$ 为各子树最大的 $\text{mex}$ ，总垫脚石数为各子树垫脚石数之和。

本质上这是一个二维树形背包，容易写出合并转移方程。

注意用临时数组进行背包以隔离新旧状态，具体转移不再赘述，如有需要详见代码。

考虑根节点的转移。如果 $u$ 不是垫脚石，显然应该枚举使用的垫脚石数量更新状态。

你可能会发现一个问题。如果 $u$ 自己是垫脚石，那么它到底能不能使用垫脚石呢？

仔细回想垫脚石的定义，它是子树内权值严格大于子树 $\text{mex}$ 的点。如果 $u$ 自己是垫脚石，在使用垫脚石之前它的 $\text{mex}$ 必然与各个子树最大的 $\text{mex}$ 相等。那根据垫脚石的定义，这部分垫脚石数不能使用的，否则将会违反定义！

难道先合并的做法是错的吗？

实则不然，不妨考虑违反定义意味着什么。

违反定义则意味着在最优解中这个垫脚石实际上在更早之前就应该被使用，这样权值才不会大于此时的 $\text{mex}$ 。那这种情况实际上已经在 $u$ 不是垫脚石的情况里转移过了，因此这种可能是多余的，我们不需要写。

时间复杂度 $O(n^4)$ ，期望得分 $32\text{pts}$ ，实际得分 $48\text{pts}$ ，和 $O(n^3)$ 一个分，常数小快到飞起。

#include <bits/stdc++.h>
//#define int int64_t
//#define int __int128
//#define MOD (1000000007)
//#define eps (1e-6)
#define endl '\n'
#define debug_endl cout<<endl;
#define debug cout<<"debug"<<endl;
using namespace std;
const int MAXN=370;
const int MAXM=MAXN;
int T,n,m;
vector<int> a[MAXN];
int dp[MAXN][MAXN][MAXN],siz[MAXN],ans;
int tmp[MAXN][MAXN],dp_v[MAXN][MAXN];
inline void init(){
	ans=0;
	for(int i=1;i<=n;++i){
		a[i].clear();
	}
}
void dfs(int u){
	for(int v:a[u]){//先递归以防全局数组数据污染
		dfs(v);
	}
	siz[u]=0;//为了服务背包，siz在dfs内表示当前合并了多少个点，根节点的转移特殊所以放最后，siz自然初始为0
	for(int i=0;i<=n;++i){//mex最大值是子树大小
		for(int j=0;j<=n;++j){
			dp_v[i][j]=dp[u][i][j]=INT32_MIN;
		}
	}
	dp_v[0][0]=0;//空状态，无意义，转移用
	for(int v:a[u]){//合并子树
		for(int i=0;i<=siz[u]+siz[v];++i){
			for(int j=0;j<=siz[u]+siz[v];++j){
				tmp[i][j]=INT32_MIN;
			}
		}
		for(int i0=0;i0<=siz[u];++i0){
			for(int j0=0;j0<=siz[u];++j0){
				if(dp_v[i0][j0]==INT32_MIN) continue;//初始状态不合法
				for(int i1=0;i1<=siz[v];++i1){
					for(int j1=0;j1<=siz[v];++j1){
						if(dp[v][i1][j1]==INT32_MIN) continue;
						int i2=max(i0,i1),j2=j0+j1;
						tmp[i2][j2]=max(tmp[i2][j2],dp_v[i0][j0]+dp[v][i1][j1]);
					}
				}
			}
		}
		siz[u]+=siz[v];
		for(int i=0;i<=siz[u];++i){
			for(int j=0;j<=siz[u];++j){
				dp_v[i][j]=tmp[i][j];
			}
		}
	}
	for(int i=0;i<=siz[u];++i){//考虑根节点u
		for(int j=0;j<=siz[u];++j){
			if(dp_v[i][j]==INT32_MIN) continue;
			dp[u][i][j+1]=max(dp[u][i][j+1],dp_v[i][j]+i);//选择u作为垫脚石
			for(int dj=0;dj<=j;++dj){//消耗dj个垫脚石给自己抬升
				int i1=i+dj+1,j1=j-dj;
				if(i1<=siz[u]+2){
					dp[u][i1][j1]=max(dp[u][i1][j1],dp_v[i][j]+i1);
				}
			}
		}
	}
	++siz[u];//加入根节点
}
signed main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--){
		cin>>n>>m;
		init();
		for(int i=2;i<=n;++i){
			int p;
			cin>>p;
			a[p].emplace_back(i);
		}
		dfs(1);
		for(int i=0;i<=n;++i){
			for(int j=0;j<=n;++j){
				ans=max(ans,dp[1][i][j]);
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

洛谷提交记录：https://www.luogu.com.cn/record/279623674

瓶颈在于背包合并。

前缀max预处理优化， $O(n^3)$

注意到若 $i_2=i_0$ 则一定有 $i_1\leq i_0$ ，那么取值只跟 $j_1$ 有关， $i_2=i_1$ 同理。

因此我们可以枚举固定 $i_2$ ，预处理 $i_0$ 和 $i_1$ 的前缀最大值减少一层循环。

时间复杂度 $0(n^3)$ ，期望得分 $48\text{pts}$ ，实际得分 $48\text{pts}$ 。

#include <bits/stdc++.h>
//#define int int64_t
//#define int __int128
//#define MOD (1000000007)
//#define eps (1e-6)
#define endl '\n'
#define debug_endl cout<<endl;
#define debug cout<<"debug"<<endl;
using namespace std;
const int MAXN=370;
const int MAXM=MAXN;
int T,n,m;
vector<int> a[MAXN];
int dp[MAXN][MAXN][MAXN],siz[MAXN],ans;
int pre_max_v[MAXN][MAXN],pre_max_u[MAXN][MAXN];//前缀最大值优化预处理数组
int tmp[MAXN][MAXN],dp_v[MAXN][MAXN];
inline void init(){
	ans=0;
	for(int i=1;i<=n;++i){
		a[i].clear();
	}
}
void dfs(int u){
	for(int v:a[u]){
		dfs(v);
	}
	siz[u]=0;//为了服务背包，siz在dfs内表示当前合并了多少个点，根节点的转移特殊所以放最后，siz自然初始为0
	for(int i=0;i<=n;++i){//mex最大值是子树大小
		for(int j=0;j<=n;++j){
			dp_v[i][j]=dp[u][i][j]=INT32_MIN;
		}
	}
	dp_v[0][0]=0;//空状态，无意义，转移用
	for(int v:a[u]){//合并子树
		for(int i=0;i<=siz[u]+siz[v];++i){
			for(int j=0;j<=siz[u]+siz[v];++j){
				tmp[i][j]=INT32_MIN;
			}
		}
		for(int i0=0;i0<=max(siz[u],siz[v]);++i0){//在不考虑使用垫脚石的情况下，mex最大是子树的max{mex}+1
			for(int j0=0;j0<=siz[u];++j0){
				pre_max_u[i0][j0]=max(i0>0?pre_max_u[i0-1][j0]:INT32_MIN,dp_v[i0][j0]);
			}
		}
		for(int i1=0;i1<=max(siz[u],siz[v]);++i1){
			for(int j1=0;j1<=siz[v];++j1){
				pre_max_v[i1][j1]=max(i1>0?pre_max_v[i1-1][j1]:INT32_MIN,dp[v][i1][j1]);
			}
		}
		for(int i2=0;i2<=max(siz[u],siz[v]);++i2){
			for(int j0=0;j0<=siz[u];++j0){
				for(int j1=0;j1<=siz[v];++j1){
					int j2=j0+j1;
					if(dp_v[i2][j0]!=INT32_MIN&&pre_max_v[i2][j1]!=INT32_MIN){//i2=i0
						tmp[i2][j2]=max(tmp[i2][j2],dp_v[i2][j0]+pre_max_v[i2][j1]);
					}
					if(dp[v][i2][j1]!=INT32_MIN&&pre_max_u[i2][j0]!=INT32_MIN){//i2=i1
						tmp[i2][j2]=max(tmp[i2][j2],dp[v][i2][j1]+pre_max_u[i2][j0]);
					}
				}
			}
		}
		siz[u]+=siz[v];
		for(int i=0;i<=siz[u];++i){
			for(int j=0;j<=siz[u];++j){
				dp_v[i][j]=tmp[i][j];
			}
		}
	}
	for(int i=0;i<=siz[u];++i){//考虑根节点u
		for(int j=0;j<=siz[u];++j){
			if(dp_v[i][j]==INT32_MIN) continue;
			dp[u][i][j+1]=max(dp[u][i][j+1],dp_v[i][j]+i);//选择u作为垫脚石
			for(int dj=0;dj<=j;++dj){//消耗dj个垫脚石给自己抬升
				int i1=i+dj+1,j1=j-dj;
				if(i1<=siz[u]+2){
					dp[u][i1][j1]=max(dp[u][i1][j1],dp_v[i][j]+i1);
				}
			}
		}
	}
	++siz[u];//加入根节点
}
signed main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--){
		cin>>n>>m;
		init();
		for(int i=2;i<=n;++i){
			int p;
			cin>>p;
			a[p].emplace_back(i);
		}
		dfs(1);
		for(int i=0;i<=n;++i){
			for(int j=0;j<=n;++j){
				ans=max(ans,dp[1][i][j]);
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

洛谷提交记录，比 $O(n^4)$ 快了很多：https://www.luogu.com.cn/record/279623586

我们没有用到题目给的树高 $m$ ，显然瓶颈在于状态设计。

通向正解

观察性质

这部分来源于第二篇题解，我认为这部分第二篇题解讲的是极好的，我只做也只能做补充。

暴力做法至此难以优化，注意到题面专门给了树高 $m$ ，这启发我们从链考虑问题。定义“ $u$ 贡献到 $v$ ”表示 $v$ 是 $u$ 到根节点的路径上 $\text{mex}$ 大于 $a_u$ 的最深的点。

观察性质，我们发现对于部分非叶子节点，其 $\text{mex}$ 是以某个子树为基础的。我们将这种父子之间的边称为传递边。

小问题：同一个父节点向子节点连接的传递边有几条？

父节点继承传递边连着的子节点的 $\text{mex}$ 并进行抬升，在这样的结构下，传递边连着的儿子若抬升 $\text{mex}$ 则父节点也会随之提升。它最多只由一个子节点决定，在动态规划中，这样的唯一对应关系是确定的，如果在最优结构中恰好有另外几个子节点的 $\text{mex}$ 与传递边连着的子节点相同，那只是恰好而已，请注意，传递边代表的是节点 $\text{mex}$ 的依赖关系，而不是简单的数值相等。

注意不连传递边表示各子树点权集合拼合，这是合法且可能优的，所以答案是 0 或 1 条。

我们称这些点连成的链叫做传递链，每个点一定属于唯一的一条传递链，可以发现，这样的结构是这棵树的剖分（不过注意这跟长链剖分和重链剖分不同，链的底端不一定非要是叶子节点，正如我们上面所说，一个非叶子节点可以不连传递边）。

不妨反向思考，每个点对答案的贡献在这样的剖分结构下是怎样的？

由于每个点都可以选择把自己当做垫脚石，向任意唯一个祖先贡献，则它祖先有若干条传递链，向最长的一条贡献才能最优。

我们以样例 2 为例子：

不带括号的数字是点编号，带括号的是实际填充的点权（根据题面的构造），红实边为传递边，蓝虚边为非传递边。

点 1、3 之上最长传递链长度为 1，分别贡献答案 1。
点 2、5、6 、7 之上最长传递链长度为 2，分别贡献答案 2。
点 4 之上最长传递链长度为 3，贡献答案 3。

总答案 1+2+1+3+2+2+2=13。

至此问题已经转换：如何正确剖分这棵树才能使得答案最大？

转换贡献方式， $O(nm^2)$

~~艰难地~~不难设计出状态：设 $dp[u][i][j]$ 表示 $u$ 子树所在传递链当前链长（或者说所在传递链的链上深度）为 $i$ ，**其到根节点路上经过的传递链链长（只算传递链与 $u$ 到根节点路径重合的部分，只有这部分的链可以贡献到）**为 $j$ 。

转移我们可以选择唯一一个子节点连接传递边（继承链长）并尝试更新最长链长记录，也可以不连传递边（链长为 1），然后加上自己的贡献。

容易写出转移：

$$dp[u][i][j]=j+ \max\bigg\{ \sum_{v\in son_u}dp[v][1][j], \max_{v\in son_u}\Big\{\sum_{w\in son_u,w\neq v}dp[w][1][j]+dp[v][i+1][\max(i+1,j)]\Big\} \bigg\} $$

转移很好写，注意下不可达状态的设置即可。

#include <bits/stdc++.h>
#define int int64_t
//#define int __int128
//#define MOD (1000000007)
//#define eps (1e-6)
#define endl '\n'
#define debug_endl cout<<endl;
#define debug cout<<"debug"<<endl;
using namespace std;
const int MAXN=4010;
const int MAXM=55;
int T,n,m;
vector<int> a[MAXN];
int dp[MAXN][MAXM][MAXM];
int sum[MAXM];
inline void init(){
	for(int i=1;i<=n;++i){
		a[i].clear();
	}
}	
void dfs(int u,int dep){
	if(a[u].empty()){
		for(int i=1;i<=m;++i){
			for(int j=1;j<=m;++j){
				dp[u][i][j]=(i<=j&&j<=dep?j:INT32_MIN);
			}
		}
		return ;
	}
	for(int v:a[u]){//先递归以防全局数组数据污染
		dfs(v,dep+1);
	}
	for(int i=1;i<=m;++i){
		sum[i]=0;
		for(int j=1;j<=m;++j){//非叶子节点假设都不可达，可达状态靠转移筛选
			dp[u][i][j]=INT32_MIN;
		}
	}
	for(int v:a[u]){
		for(int j=1;j<=dep;++j){
			sum[j]+=dp[v][1][j];//儿子节点深度+1，这些肯定都可达
		}
	}
	for(int i=1;i<=dep;++i){//不可能出现大于深度的链
		for(int j=i;j<=dep;++j){//历史最长不短于当前链长
			dp[u][i][j]=sum[j];
			for(int v:a[u]){
				if(dp[v][1][j]>=0&&dp[v][i+1][(j==i?i+1:j)]>=0){//可以转移
					dp[u][i][j]=max(dp[u][i][j],sum[j]-dp[v][1][j]+dp[v][i+1][(j==i?i+1:j)]);
				}
			}
			dp[u][i][j]+=j;//加上u自身贡献
		}
	}
}
signed main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--){
		cin>>n>>m;
		++m;//点高度
		init();
		for(int i=2;i<=n;++i){
			int p;
			cin>>p;
			a[p].emplace_back(i);
		}
		dfs(1,1);
		cout<<dp[1][1][1]<<endl;
	}
	return 0;
}

洛谷提交记录：https://www.luogu.com.cn/record/281352222

时间复杂度 $O(nm^2)$ ，预期得分 $76pts$ ，因为前面暴力分的 $m=360$ 太大只用这份代码硬开会 MLE，所以你需要跟前面暴力代码做一个合并，我懒得合并了就这样吧。瓶颈在状态数量。

继续艰难地观察性质，简化状态，可惜仍然 $O(nm^2)$

这部分第二篇题解我就看不懂了，而结合第一篇题解后一切变得明朗……

暴力做法中我们定义了垫脚石以区分点的作用，可在上一个做法中没有显式使用。现在我们正式定义树上的两种不同的点，看看能不能在点上发现端倪：

A类点：向自己贡献的点，即权值为自身 $\text{mex}-1$ 的点。
B类点：向祖先贡献的点，即上文所说的垫脚石。

把点拆分成两种后，考虑它们有什么不同。

考虑什么时候点才会是 A 类点

有了上个 $O(nm^2)$ 的做法我们容易发现：如果这个点它所在链不是到根节点的最长链，它会向最长链贡献，根据定义它将会是 B 类点。所以 A 类点所在链一定是到根节点的最长传递链！这同时也说明了 A 类点不连传递边的儿子一定为 B 类点。

分离原来的大 $dp$ 状态，设 $f[u][i]$ 代表 $u$ 是 A 类点，所在链（也即最长链）链长为 $i$ 。它的转移和原来的转移差不多，不再赘述，请读者自己写出来。

可 B 类点呢？~~可 B 坠机了~~

如果你手玩几个手造数据并且标出来哪些是 A 类点哪些是 B 类点的话，可能会发现存在一种最优解结构所有传递链的上半部分全是 B 类点下半部分全是 A 类点~~（其实很难发现吧）~~。

为什么？

假设现在有一条传递链从上到下是 B-A-B 型的，顺序编号为 $x,y,z$ 。传递链上抬升自身祖先也会抬升，对这条链进行分类讨论。

如果这条链是 $z$ 到根节点的最长链，那么不妨把 $z$ 改成 A 类点对祖先增加贡献，一定不劣。
如果这条链不是 $z$ 到根节点的最长链，那么 $z$ 到根节点的最长链肯定也是 $y$ 到根节点的最长链，不如把 $y$ 改成 B 类点，一定不劣。

由此，我们证明存在一种最优解结构使得传递链的上部分全是 B 类点，下部分全是 A 类点。

那么这样有什么用呢？这就有个非常天才的想法：重复信息是可压缩的。

具体来说，我们把原来的大 $dp$ 状态对两种点拆成两部分，A 类点已经说了不再重复，对于 B 类点，我们可以枚举 B 链（即一条完整的传递链的 B 类点部分）尾在哪，接上 A 类点状态。由于 A 类点出现的充要条件，记录到根节点最长链长之后 B 链的长度是锁定的，这条 B 链上所有的点的贡献也都是固定的，根本不需要单开状态去记录这坨史，这样我们就把原来 $dp$ 的其中一维当前链长状态完全剥离了出来！

设 $g[u][i]$ 表示 $u$ 是 B 类点，到根节点最长链长为 $i$ 。状态数已经达到了 $O(nm)$ ，这是里程碑式的进步。

别着急，B 类点还有一种特殊转移：依然根据 A 类点出现的充要条件，如果子树根本塞不下这个长度的 B 链，我们就只好把整棵子树全变成 B 类点了。

不难理解一个子树将会被这几种情况完全覆盖。

可能有人会思考一个小细节：假设到根节点最长链长为 $i$ ，那么这条 B 链长度是 $i$ 还是 $i-1$ 是不是一样的？

答案是：确实。因为对于链上深度为 $i$ 的点它是 A 还是 B 虽然贡献到的链不一样，但由于长度一样贡献值是一样的。

这里选择和原第一篇题解一样的，B 链长为 $i-1$ 的写法。

记$s[u][i]=\sum_{v\in son_{fa(u)}}g[v][i],h[u][i]=s[u][i]-g[u][i]$。为什么是兄弟的写法？这样只跟节点 $u$ 自身相关，好维护。

我们轻易地写出转移：

$$g[u][i]=\max\bigg\{ i\times |subt_u|, i\times (i-1)+\max_{v\in subt_u,dep_v-dep_u+1=i}\Big\{ \sum_{w\in path(u,v),w\neq u}h[w][i]+f[v][i] \Big\} \bigg\} $$

~~怎么这么难看~~

实现也很暴力，枚举 $u$ 子树的每个节点，再枚举路径计算 $s$ 和 $h$ 根据深度相应转移即可，这里记录 dfs 序列以方便遍历子树。

状态数达标，我们终于可以把 $n,m$ 开满了！

#include <bits/stdc++.h>
#define int int64_t
//#define int __int128
//#define MOD (1000000007)
//#define eps (1e-6)
#define endl '\n'
#define debug_endl cout<<endl;
#define debug cout<<"debug"<<endl;
using namespace std;
const int MAXN=8010;
const int MAXM=865;
int T,n,m;
vector<int> a[MAXN];
int f[MAXN][MAXM],g[MAXN][MAXM];
int sum[MAXM],dfn[MAXN],tot,mp[MAXN],dfm[MAXN],fa[MAXN],h[MAXN],dep[MAXN];
inline void init(){
	tot=0;
	for(int i=1;i<=n;++i){
		a[i].clear();
	}
}
void dfs1(int u,int fu){//处理dfs序方便转移g
	fa[u]=fu;
	dfn[u]=++tot;//访问时间戳
	mp[tot]=u;
	dep[u]=dep[fu]+1;
	for(int v:a[u]){
		dfs1(v,u);
	}
	dfm[u]=tot;//退出时间戳
}
void dfs(int u){
	for(int v:a[u]){//先递归以防全局数组数据污染
		dfs(v);
	}
	for(int i=1;i<=m;++i){
		sum[i]=0;
		f[u][i]=INT32_MIN;
		g[u][i]=INT32_MIN;
	}
	for(int v:a[u]){
		for(int j=1;j<=m;++j){
			sum[j]+=g[v][j];
		}
	}
	for(int i=1;i<=m;++i){
		f[u][i]=sum[i];
		for(int v:a[u]){
			f[u][i]=max(f[u][i],sum[i]-g[v][i]+f[v][i+1]);
		}
		f[u][i]+=i;
	}
	for(int j=1;j<=m;++j){
		h[u]=0;
		g[u][j]=j*(dfm[u]-dfn[u]+1);
		for(int i=dfn[u];i<=dfm[u];++i){
			int w=mp[i];
			if(i!=dfn[u]){
				h[w]=h[fa[w]]-g[w][j];
			}
			if(dep[w]-dep[u]+1==j){
				g[u][j]=max(g[u][j],h[w]+f[w][j]+(j-1)*j);
			}
			for(int v:a[w]){
				h[w]+=g[v][j];
			}
		}
	}
	
}
signed main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--){
		cin>>n>>m;
		++m;//点高度
		init();
		for(int i=2;i<=n;++i){
			int p;
			cin>>p;
			a[p].emplace_back(i);
		}
		dfs1(1,0);
		dfs(1);
		cout<<f[1][1]<<endl;//根节点肯定是A点
	}
	return 0;
}

然后 RE 全 TLE 了。

洛谷提交记录：https://www.luogu.com.cn/record/280791659

可以看到减少无用转移后快了点。

枚举深度是一层 $m$ ，遍历树进行 dp 是一层 $n$ ，每个节点最多被祖先节点统计 $m$ 次，时间复杂度 $O(nm^2)$ 。不过这个对比上一个 $O(nm^2)$ 的优点是显然的，时间复杂度瓶颈不在于状态而在于枚举计算 $g$ 。

上科技！数据结构牛逼！树状数组维护 $O(nm\log n)$

这个每次枚举子树节点还要再枚举路径看着就很蠢，这时候我们 $h$ 和 $s$ 的定义优势就显现出来了，它只跟 $u$ 有关，就容易使用数据结构维护。

$h$ 数组是节点 $v$ 到其祖先 $u$ 路径上每个点 $g$ 的和，而我们 dp 又是自下向上的，考虑用树状数组维护每一个点的 $h[v][i]$ ，每向上走一个点，就将子树内所有点的 $h[v][i]$ 更新，这是子树加操作。

只需要子树操作单点查询而已，按照第一篇题解那样 dfs 序树状数组维护即可。

进入点 $u$ 先把所有儿子节点的 $h$ 算好加入树状数组，然后依然枚举子树每个点 $v$ ，进行单点查询贡献，计算 $u$ 的答案。

#include <bits/stdc++.h>
#define int int64_t
//#define int __int128
//#define MOD (1000000007)
//#define eps (1e-6)
#define endl '\n'
#define debug_endl cout<<endl;
#define debug cout<<"debug"<<endl;
using namespace std;
const int MAXN=8010;
const int MAXM=805;
int T,n,m;
vector<int> a[MAXN];
int f[MAXN][MAXM],g[MAXN][MAXM];
int sum[MAXM],dfn[MAXN],tot,mp[MAXN],dfm[MAXN],fa[MAXN],h[MAXN],dep[MAXN];
struct BIT{
	int c[MAXN];
	inline int lowbit(int x){
		return x&(-x);
	}
	inline void add(int p,int k){
		for(int i=p;i<=n;i+=lowbit(i)){
			c[i]+=k;
		}
	} 
	inline int query(int p){
		int res=0;
		for(int i=p;i>0;i-=lowbit(i)){
			res+=c[i];
		}
		return res;
	} 
	inline void clear(){
		for(int i=1;i<=n;++i){
			c[i]=0;
		}
	}
};
BIT tr[MAXM];
inline void init(){
	tot=0;
	for(int i=1;i<=m;++i){
		tr[i].clear();
	}
	for(int i=1;i<=n;++i){
		a[i].clear();
	}
}
void dfs1(int u,int fu){//处理dfs序方便转移g
	fa[u]=fu;
	dfn[u]=++tot;//访问时间戳
	mp[tot]=u;
	dep[u]=dep[fu]+1;
	for(int v:a[u]){
		dfs1(v,u);
	}
	dfm[u]=tot;//退出时间戳
}
void dfs(int u){
	for(int v:a[u]){//先递归以防全局数组数据污染
		dfs(v);
	}
	for(int i=1;i<=m;++i){
		sum[i]=0;
		f[u][i]=INT32_MIN;
		g[u][i]=INT32_MIN;
	}
	for(int v:a[u]){
		for(int j=1;j<=m;++j){
			sum[j]+=g[v][j];
		}
	}
	for(int i=1;i<=m;++i){
		f[u][i]=sum[i];
		g[u][i]=i*(dfm[u]-dfn[u]+1);
		for(int v:a[u]){
			f[u][i]=max(f[u][i],sum[i]-g[v][i]+f[v][i+1]);
		}
		f[u][i]+=i;
	}
	for(int v:a[u]){
		for(int i=1;i<=m;++i){
			tr[i].add(dfn[v],sum[i]-g[v][i]);//来到父节点，对子树每个点加上偏移量
			tr[i].add(dfm[v]+1,-(sum[i]-g[v][i]));
		}
	}
	for(int i=dfn[u];i<=dfm[u];++i){//这样我们就省去了遍历链
		int w=mp[i];
		int j=dep[w]-dep[u]+1;
		g[u][j]=max(g[u][j],tr[j].query(i)+f[w][j]+(j-1)*j);
	}
	
}
signed main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--){
		cin>>n>>m;
		++m;//点高度
		init();
		for(int i=2;i<=n;++i){
			int p;
			cin>>p;
			a[p].emplace_back(i);
		}
		dfs1(1,0);
		dfs(1);
		cout<<f[1][1]<<endl;//根节点肯定是A点
	}
	return 0;
}

洛谷提交记录：https://www.luogu.com.cn/record/280792580

时间复杂度 $O(nm\log n)$ ，恭喜你至此已经可以通过此题。

还有高手？优化最后的冗余以及最终的魔法：长链剖分优化 dp $O(nm)$

我们不难发现还是计算了冗余数据。对于固定链长，我们明明只想知道对应深度的答案，而我们却把这层点全跑了一遍，难道不能把一层点的信息全压在一起吗？

~~聪明的你一定想到了线段树合并~~ OK 写完发现常数过大直接喜提跟 $O(nm^2)$ 一样的分。

那怎么办？使用神秘指针科技之长链剖分。

设 $S[u][i]$ 表示 $u$ 子树子树内深度为 $i$ 这一整层点在计算 $g[u][i]$ 时的贡献。

有转移 $S[u][i]=\max_{v\in son_u}S[v][i-1]+h[v][i]$ ，这揭示了转移的下标偏移操作。

实现中，我们剥离当前 dp 的链长 $i$ ，套在外部从大到小循环（因为 $f$ 的转移是从大到小的）便于 $g$ 转移。复用长儿子，通过正确分配内存地址（把长儿子的内存地址开头设为 $u$ 的下一个，这样 $u$ 就可以顺延了），并暴力合并短儿子，由于长链剖分的长链互不相交，每条长链又最多暴力合并一次，这是 $O(n)$ 的。

而上一个版本中“子树加”操作就可以通过维护懒标记数组 $delta[u]$ 实现。

外部循环 $m$ 次，dfs 是 $O(n)$ 的，总时间复杂度 $O(nm)$ 。

#include <bits/stdc++.h>
#define int int64_t
//#define int __int128
//#define MOD (1000000007)
//#define eps (1e-6)
#define endl '\n'
#define debug_endl cout<<endl;
#define debug cout<<"debug"<<endl;
using namespace std;
const int MAXN=8010;
const int MAXM=810;
int T;
vector<int> a[MAXN];
int *sh[MAXN];//每个节点的长链数组对应头地址，sh[u][i]维护u节点子树里构造B链长为i的最大对g[u][i]转移贡献
int pool[MAXN];//声明一块空内存池
int delta[MAXN];//长链数组偏移量
int pool_size;
int n,m;
int son[MAXN],height[MAXN],f_now[MAXN],f_nex[MAXN],g[MAXN],siz[MAXN];
inline void initdp(){
	fill(sh+1,sh+n+1,nullptr);
	memset(delta,0,(n+1)*sizeof(int));
	pool_size=0;
}
inline void init(){
	for(int i=1;i<=n;++i){
		a[i].clear();
		f_now[i]=f_nex[i]=g[i]=INT32_MIN;
		son[i]=0;
	}
}
void dfs1(int u){
	siz[u]=1;
	for(int v:a[u]){
		dfs1(v);
		siz[u]+=siz[v];
		if(height[son[u]]<height[v]){
			son[u]=v;
		}
	}
	height[u]=height[son[u]]+1;
}
void dfs(int u,int l){
	if(sh[u]==nullptr){//短儿子，没有指定内存
		sh[u]=pool+pool_size;
		pool_size+=height[u];
		fill(sh[u],sh[u]+height[u],INT32_MIN);//分配u节点的长链内存并初始化为不可达状态
	}
	if(son[u]){//有长儿子就分配位置，沿用长儿子内存
		sh[son[u]]=sh[u]+1;
	}
	int sum_g=0;
	for(int v:a[u]){
		dfs(v,l);
		sum_g+=g[v];
	}
	//f的转移跟O(nmlogn)差不多，对应着改写即可
	f_now[u]=sum_g;
	for(int v:a[u]){
		f_now[u]=max(f_now[u],sum_g-g[v]+f_nex[v]);
	}
	f_now[u]+=l;
	//g的转移，先沿用长儿子
	if(son[u]){
		delta[u]=delta[son[u]]+sum_g-g[son[u]];//计算长儿子链新增的h
	}
	for(int v:a[u]){//计算
		if(v!=son[u]){
			int dv=delta[v]+sum_g-g[v]-delta[u];//记得这里delta[u]是对长儿子打的标记，短儿子需要减去抵消
			for(int i=1;i<=height[v];++i){//暴力合并短链
				sh[u][i+1]=max(sh[u][i+1],sh[v][i]+dv);
			}
		}
	}
	sh[u][1]=f_now[u]-delta[u];//若选u为B链终点，还要计入f[u]的贡献
	g[u]=l*siz[u];
	if(height[u]>=l)
		g[u]=max(g[u],l*(l-1)+sh[u][l]+delta[u]);
}
void solve(){
	cin>>n>>m;
	++m;
	init();
	for(int i=2;i<=n;++i){
		int p;
		cin>>p;
		a[p].emplace_back(i);
	}
	dfs1(1);
	for(int l=m;l>=1;--l){//f转移顺序是i+1->i，这里对应
		initdp();
		dfs(1,l);
		copy(f_now+1,f_now+n+1,f_nex+1);//这一轮的now就是下一轮转移用的nex
	}
	cout<<f_now[1]<<endl;
}
signed main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--){
		solve();
	}
	return 0;
}

洛谷提交记录：https://www.luogu.com.cn/record/281348124 时间是 $O(nm\log n)$ 的一半多。

后记

赛场上看到 T2T3T4 我的心情是绝望的，不止一次埋头苦笑，无力感涌上全身，却不得不强行打起精神来。

罚坐，时间无意义地流逝，直到最后。

我没有什么心情波动，从最开始我就知道，我大抵已经死了。

半年后，我回到了这里。面对一座山，我曾想象过爬上峭壁有多么吃力，行于山脊有多么惊险，穿过迷雾有多么困难……可我没想过，根本无路可走，我要做的是一点点从石缝中扣出一条隧道，每一步都是阻碍。

常叹世人之智，乃余平生所不能及。然终日复长嗟，徒然无益。

十年之后，尚能追忆，足矣。

洛谷P14637 [NOIP2025] 树的价值题解与碎碎念

前言

部分记号表

暴力

暴力树上背包 O(n4)O(n^4)O(n4)

前缀max预处理优化，O(n3)O(n^3)O(n3)

通向正解

观察性质

小问题：同一个父节点向子节点连接的传递边有几条？

不妨反向思考，每个点对答案的贡献在这样的剖分结构下是怎样的？

转换贡献方式，O(nm2)O(nm^2)O(nm2)

继续艰难地观察性质，简化状态，可惜仍然 O(nm2)O(nm^2)O(nm2)​

考虑什么时候点才会是 A 类点

为什么？

可能有人会思考一个小细节：假设到根节点最长链长为 iii，那么这条 B 链长度是 iii 还是 i−1i-1i−1 是不是一样的？

上科技！数据结构牛逼！树状数组维护 O(nmlog⁡n)O(nm\log n)O(nmlogn)

还有高手？优化最后的冗余以及最终的魔法：长链剖分优化 dp O(nm)O(nm)O(nm)

后记

评论

还没有账户？

登录