这部分来源于第二篇题解我认为这部分第二篇题解讲的是极好的我只做也只能做补充。暴力做法至此难以优化注意到题面专门给了树高 这启发我们从链考虑问题。定义“ 贡献到 ”表示 是 到根节点的路径上 大于 ​ 的最深的点。观察性质我们发现对于部分非叶子节点其 ​ 是以某个子树为基础的。我们将这种父子之间的边称为传递边。小问题同一个父节点向子节点连接的传递边有几条父节点继承传递边连着的子节点的 并进行抬升在这样的结构下传递边连着的儿子若抬升 则父节点也会随之提升。它最多只由一个子节点决定在动态规划中这样的唯一对应关系是确定的如果在最优结构中恰好有另外几个子节点的 与传递边连着的子节点相同那只是恰好而已请注意传递边代表的是节点 ​ 的依赖关系而不是简单的数值相等。注意不连传递边表示各子树点权集合拼合这是合法且可能优的所以答案是 0 或 1 条。我们称这些点连成的链叫做传递链每个点一定属于唯一的一条传递链可以发现这样的结构是这棵树的剖分不过注意这跟长链剖分和重链剖分不同链的底端不一定非要是叶子节点正如我们上面所说一个非叶子节点可以不连传递边。不妨反向思考每个点对答案的贡献在这样的剖分结构下是怎样的由于每个点都可以选择把自己当做垫脚石向任意唯一个祖先贡献则它祖先有若干条传递链向最长的一条贡献才能最优。我们以样例 2 为例子不带括号的数字是点编号带括号的是实际填充的点权根据题面的构造红实边为传递边蓝虚边为非传递边。点 1、3 之上最长传递链长度为 1分别贡献答案 1。点 2、5、6 、7 之上最长传递链长度为 2分别贡献答案 2。点 4 之上最长传递链长度为 3贡献答案 3。总答案 121322213。至此问题已经转换如何正确剖分这棵树才能使得答案最大转换贡献方式艰难地不难设计出状态设 表示 子树所在传递链当前链长或者说所在传递链的链上深度为 其到根节点路上经过的传递链链长只算传递链与 到根节点路径重合的部分只有这部分的链可以贡献到为 ​。转移我们可以选择唯一一个子节点连接传递边继承链长并尝试更新最长链长记录也可以不连传递边链长为 1然后加上自己的贡献。容易写出转移转移很好写注意下不可达状态的设置即可。#include bits/stdc.h #define int int64_t //#define int __int128 //#define MOD (1000000007) //#define eps (1e-6) #define endl \n #define debug_endl coutendl; #define debug coutdebugendl; using namespace std; const int MAXN4010; const int MAXM55; int T,n,m; vectorint a[MAXN]; int dp[MAXN][MAXM][MAXM]; int sum[MAXM]; inline void init(){ for(int i1;in;i){ a[i].clear(); } } void dfs(int u,int dep){ if(a[u].empty()){ for(int i1;im;i){ for(int j1;jm;j){ dp[u][i][j](ijjdep?j:INT32_MIN); } } return ; } for(int v:a[u]){//先递归以防全局数组数据污染 dfs(v,dep1); } for(int i1;im;i){ sum[i]0; for(int j1;jm;j){//非叶子节点假设都不可达可达状态靠转移筛选 dp[u][i][j]INT32_MIN; } } for(int v:a[u]){ for(int j1;jdep;j){ sum[j]dp[v][1][j];//儿子节点深度1这些肯定都可达 } } for(int i1;idep;i){//不可能出现大于深度的链 for(int ji;jdep;j){//历史最长不短于当前链长 dp[u][i][j]sum[j]; for(int v:a[u]){ if(dp[v][1][j]0dp[v][i1][(ji?i1:j)]0){//可以转移 dp[u][i][j]max(dp[u][i][j],sum[j]-dp[v][1][j]dp[v][i1][(ji?i1: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); cinT; while(T--){ cinnm; m;//点高度 init(); for(int i2;in;i){ int p; cinp; a[p].emplace_back(i); } dfs(1,1); coutdp[1][1][1]endl; } return 0; }洛谷提交记录https://www.luogu.com.cn/record/281352222时间复杂度 ​​​预期得分 因为前面暴力分的 太大只用这份代码硬开会 MLE所以你需要跟前面暴力代码做一个合并我懒得合并了就这样吧。瓶颈在状态数量。继续艰难地观察性质简化状态可惜仍然 ​这部分第二篇题解我就看不懂了而结合第一篇题解后一切变得明朗……暴力做法中我们定义了垫脚石以区分点的作用可在上一个做法中没有显式使用。现在我们正式定义树上的两种不同的点看看能不能在点上发现端倪A类点向自己贡献的点即权值为自身 的点。B类点向祖先贡献的点即上文所说的垫脚石。把点拆分成两种后考虑它们有什么不同。考虑什么时候点才会是 A 类点有了上个 ​ 的做法我们容易发现如果这个点它所在链不是到根节点的最长链它会向最长链贡献根据定义它将会是 B 类点。所以 A 类点所在链一定是到根节点的最长传递链这同时也说明了 A 类点不连传递边的儿子一定为 B 类点。分离原来的大 状态设 代表 是 A 类点所在链也即最长链链长为 ​。它的转移和原来的转移差不多不再赘述请读者自己写出来。可 B 类点呢可 B 坠机了如果你手玩几个手造数据并且标出来哪些是 A 类点哪些是 B 类点的话可能会发现存在一种最优解结构所有传递链的上半部分全是 B 类点下半部分全是 A 类点其实很难发现吧。为什么假设现在有一条传递链从上到下是 B-A-B 型的顺序编号为 。传递链上抬升自身祖先也会抬升对这条链进行分类讨论。如果这条链是 到根节点的最长链那么不妨把 改成 A 类点对祖先增加贡献一定不劣。如果这条链不是 到根节点的最长链那么 到根节点的最长链肯定也是 到根节点的最长链不如把 改成 B 类点一定不劣。由此我们证明存在一种最优解结构使得传递链的上部分全是 B 类点下部分全是 A 类点。那么这样有什么用呢这就有个非常天才的想法重复信息是可压缩的。具体来说我们把原来的大 状态对两种点拆成两部分A 类点已经说了不再重复对于 B 类点我们可以枚举 B 链即一条完整的传递链的 B 类点部分尾在哪接上 A 类点状态。由于 A 类点出现的充要条件记录到根节点最长链长之后 B 链的长度是锁定的这条 B 链上所有的点的贡献也都是固定的根本不需要单开状态去记录这坨史这样我们就把原来 的其中一维当前链长状态完全剥离了出来设 表示 是 B 类点到根节点最长链长为 。状态数已经达到了 这是里程碑式的进步。别着急B 类点还有一种特殊转移依然根据 A 类点出现的充要条件如果子树根本塞不下这个长度的 B 链我们就只好把整棵子树全变成 B 类点了。不难理解一个子树将会被这几种情况完全覆盖。可能有人会思考一个小细节假设到根节点最长链长为 那么这条 B 链长度是 还是 是不是一样的答案是确实。因为对于链上深度为 的点它是 A 还是 B 虽然贡献到的链不一样但由于长度一样贡献值是一样的。这里选择和原第一篇题解一样的B 链长为 的写法。记。为什么是兄弟的写法这样只跟节点 自身相关好维护。我们轻易地写出转移怎么这么难看实现也很暴力枚举 子树的每个节点再枚举路径计算 和 ​​ 根据深度相应转移即可这里记录 dfs 序列以方便遍历子树。状态数达标我们终于可以把 开满了#include bits/stdc.h #define int int64_t //#define int __int128 //#define MOD (1000000007) //#define eps (1e-6) #define endl \n #define debug_endl coutendl; #define debug coutdebugendl; using namespace std; const int MAXN8010; const int MAXM865; int T,n,m; vectorint 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(){ tot0; for(int i1;in;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 i1;im;i){ sum[i]0; f[u][i]INT32_MIN; g[u][i]INT32_MIN; } for(int v:a[u]){ for(int j1;jm;j){ sum[j]g[v][j]; } } for(int i1;im;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][i1]); } f[u][i]i; } for(int j1;jm;j){ h[u]0; g[u][j]j*(dfm[u]-dfn[u]1); for(int idfn[u];idfm[u];i){ int wmp[i]; if(i!dfn[u]){ h[w]h[fa[w]]-g[w][j]; } if(dep[w]-dep[u]1j){ 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); cinT; while(T--){ cinnm; m;//点高度 init(); for(int i2;in;i){ int p; cinp; a[p].emplace_back(i); } dfs1(1,0); dfs(1); coutf[1][1]endl;//根节点肯定是A点 } return 0; }然后 RE 全 TLE 了。洛谷提交记录https://www.luogu.com.cn/record/280791659可以看到减少无用转移后快了点。枚举深度是一层 遍历树进行 dp 是一层 每个节点最多被祖先节点统计 次时间复杂度 。不过这个对比上一个 的优点是显然的时间复杂度瓶颈不在于状态而在于枚举计算 ​。上科技数据结构牛逼树状数组维护这个每次枚举子树节点还要再枚举路径看着就很蠢这时候我们 和 的定义优势就显现出来了它只跟 有关就容易使用数据结构维护。数组是节点 到其祖先 路径上每个点 的和而我们 dp 又是自下向上的考虑用树状数组维护每一个点的 每向上走一个点就将子树内所有点的 更新这是子树加操作。只需要子树操作单点查询而已按照第一篇题解那样 dfs 序树状数组维护即可。进入点 先把所有儿子节点的 算好加入树状数组然后依然枚举子树每个点 进行单点查询贡献计算 ​ 的答案。#include bits/stdc.h #define int int64_t //#define int __int128 //#define MOD (1000000007) //#define eps (1e-6) #define endl \n #define debug_endl coutendl; #define debug coutdebugendl; using namespace std; const int MAXN8010; const int MAXM805; int T,n,m; vectorint 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);