企业官网建设流程全解析

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

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

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

两篇神犇的题解：

1. 20_200（下文称作“第一篇题解”）
2. 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 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预处理优化，

注意到若 则一定有 ，那么取值只跟 有关， 同理。

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

时间复杂度 ，期望得分 ，实际得分 。

#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;