本文去掉代码全文共 4800 字。这篇博客并非完全意义上的题解主要是对我学习这道题的思路回顾与总结基于以下两篇题解融合和补充所以记号不是我原创的我觉得尤其是第二篇题解定义的名词非常形象易懂直接抄了以及一些碎碎念。写了很多细节问题都是我在学习这个题时思考过的所以这篇文章非常长。两篇神犇的题解20_200下文称作“第一篇题解”tiger2005下文称作“第二篇题解”因为我是蒟蒻我已经尽量在让这篇题解启发式了qwq所以对于“显而易见的结论”讲述的废话可能很多请巨佬们多多批评指教。由于文章太长写作周期也长精修困难。如有不解请敲在讨论区我若看到一定会尽力修正表述。部分记号表记号含义节点的子节点集节点的子树点集节点的父节点节点的子树点集大小暴力这部分会有两个复杂度的做法但均为暴力及其优化与正解关联不大。但能从中初步理解某些性质个人感觉还是比较重要的。由于本人是蒟蒻这个暴力对我来说也是个难点之一本着彻底学透的想法这部分也会很长可选择跳过。考虑一个非常劣的贪心从下到上对每一层点按层分配数值叶子结点是 其父节点是 ……不用我说也知道这东西没有分。那么为什么是极劣的呢我们发现在这个策略里每个点都对自身 有贡献这使得大量节点没有对祖先进行贡献而被浪费因此一个特殊点便十分显然有一些点不对自己的 做贡献而是留给祖先这部分点我们称之为“垫脚石”。垫脚石的严格定义自身权值严格大于自身 的点。因此根据这些特殊点设计状态设 为 子树根节点 为 子树内有 个垫脚石即有 个点满足 。两位神犇对于这一暴力是完全口胡的然而蒟蒻如我连这个暴力都无法写好因此也将讲解一下。暴力树上背包根节点需要决策自身所以先不着急考虑根节点以及使用垫脚石。设临时数组 表示当前合并的所有子树的 为有 个垫脚石。初始状态为空其余状态全部设置为极小值表示不可能。合并的过程中总 为各子树最大的 总垫脚石数为各子树垫脚石数之和。本质上这是一个二维树形背包容易写出合并转移方程。注意用临时数组进行背包以隔离新旧状态具体转移不再赘述如有需要详见代码。考虑根节点的转移。如果 不是垫脚石显然应该枚举使用的垫脚石数量更新状态。你可能会发现一个问题。如果 自己是垫脚石那么它到底能不能使用垫脚石呢仔细回想垫脚石的定义它是子树内权值严格大于子树 的点。如果 自己是垫脚石在使用垫脚石之前它的 必然与各个子树最大的 相等。那根据垫脚石的定义这部分垫脚石数不能使用的否则将会违反定义难道先合并的做法是错的吗实则不然不妨考虑违反定义意味着什么。违反定义则意味着在最优解中这个垫脚石实际上在更早之前就应该被使用这样权值才不会大于此时的 。那这种情况实际上已经在 不是垫脚石的情况里转移过了因此这种可能是多余的我们不需要写。时间复杂度 期望得分 实际得分 和 一个分常数小快到飞起。#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 MAXN370; const int MAXMMAXN; int T,n,m; vectorint a[MAXN]; int dp[MAXN][MAXN][MAXN],siz[MAXN],ans; int tmp[MAXN][MAXN],dp_v[MAXN][MAXN]; inline void init(){ ans0; for(int i1;in;i){ a[i].clear(); } } void dfs(int u){ for(int v:a[u]){//先递归以防全局数组数据污染 dfs(v); } siz[u]0;//为了服务背包siz在dfs内表示当前合并了多少个点根节点的转移特殊所以放最后siz自然初始为0 for(int i0;in;i){//mex最大值是子树大小 for(int j0;jn;j){ dp_v[i][j]dp[u][i][j]INT32_MIN; } } dp_v[0][0]0;//空状态无意义转移用 for(int v:a[u]){//合并子树 for(int i0;isiz[u]siz[v];i){ for(int j0;jsiz[u]siz[v];j){ tmp[i][j]INT32_MIN; } } for(int i00;i0siz[u];i0){ for(int j00;j0siz[u];j0){ if(dp_v[i0][j0]INT32_MIN) continue;//初始状态不合法 for(int i10;i1siz[v];i1){ for(int j10;j1siz[v];j1){ if(dp[v][i1][j1]INT32_MIN) continue; int i2max(i0,i1),j2j0j1; tmp[i2][j2]max(tmp[i2][j2],dp_v[i0][j0]dp[v][i1][j1]); } } } } siz[u]siz[v]; for(int i0;isiz[u];i){ for(int j0;jsiz[u];j){ dp_v[i][j]tmp[i][j]; } } } for(int i0;isiz[u];i){//考虑根节点u for(int j0;jsiz[u];j){ if(dp_v[i][j]INT32_MIN) continue; dp[u][i][j1]max(dp[u][i][j1],dp_v[i][j]i);//选择u作为垫脚石 for(int dj0;djj;dj){//消耗dj个垫脚石给自己抬升 int i1idj1,j1j-dj; if(i1siz[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); cinT; while(T--){ cinnm; init(); for(int i2;in;i){ int p; cinp; a[p].emplace_back(i); } dfs(1); for(int i0;in;i){ for(int j0;jn;j){ ansmax(ans,dp[1][i][j]); } } coutansendl; } return 0; }洛谷提交记录https://www.luogu.com.cn/record/279623674瓶颈在于背包合并。前缀max预处理优化注意到若 则一定有 那么取值只跟 有关 同理。因此我们可以枚举固定 预处理 和 的前缀最大值减少一层循环。时间复杂度 期望得分 实际得分 。#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 MAXN370; const int MAXMMAXN; int T,n,m; vectorint 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(){ ans0; for(int i1;in;i){ a[i].clear(); } } void dfs(int u){ for(int v:a[u]){ dfs(v); } siz[u]0;//为了服务背包siz在dfs内表示当前合并了多少个点根节点的转移特殊所以放最后siz自然初始为0 for(int i0;in;i){//mex最大值是子树大小 for(int j0;jn;j){ dp_v[i][j]dp[u][i][j]INT32_MIN; } } dp_v[0][0]0;//空状态无意义转移用 for(int v:a[u]){//合并子树 for(int i0;isiz[u]siz[v];i){ for(int j0;jsiz[u]siz[v];j){ tmp[i][j]INT32_MIN; } } for(int i00;i0max(siz[u],siz[v]);i0){//在不考虑使用垫脚石的情况下mex最大是子树的max{mex}1 for(int j00;j0siz[u];j0){ pre_max_u[i0][j0]max(i00?pre_max_u[i0-1][j0]:INT32_MIN,dp_v[i0][j0]); } } for(int i10;i1max(siz[u],siz[v]);i1){ for(int j10;j1siz[v];j1){ pre_max_v[i1][j1]max(i10?pre_max_v[i1-1][j1]:INT32_MIN,dp[v][i1][j1]); } } for(int i20;i2max(siz[u],siz[v]);i2){ for(int j00;j0siz[u];j0){ for(int j10;j1siz[v];j1){ int j2j0j1; if(dp_v[i2][j0]!INT32_MINpre_max_v[i2][j1]!INT32_MIN){//i2i0 tmp[i2][j2]max(tmp[i2][j2],dp_v[i2][j0]pre_max_v[i2][j1]); } if(dp[v][i2][j1]!INT32_MINpre_max_u[i2][j0]!INT32_MIN){//i2i1 tmp[i2][j2]max(tmp[i2][j2],dp[v][i2][j1]pre_max_u[i2][j0]); } } } } siz[u]siz[v]; for(int i0;isiz[u];i){ for(int j0;jsiz[u];j){ dp_v[i][j]tmp[i][j]; } } } for(int i0;isiz[u];i){//考虑根节点u for(int j0;jsiz[u];j){ if(dp_v[i][j]INT32_MIN) continue; dp[u][i][j1]max(dp[u][i][j1],dp_v[i][j]i);//选择u作为垫脚石 for(int dj0;djj;dj){//消耗dj个垫脚石给自己抬升 int i1idj1,j1j-dj; if(i1siz[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); cinT; while(T--){ cinnm; init(); for(int i2;in;i){ int p; cinp; a[p].emplace_back(i); } dfs(1); for(int i0;in;i){ for(int j0;jn;j){ ansmax(ans,dp[1][i][j]); } } coutansendl; } return 0;