AT_abc416_f 题解
Moya_Rao
·
·
题解
某机房同学说此题简化版都是紫，有点恐怖。但是发现这个 F 其实上并没有想象中那么难，之前评紫或许是因为远古题评分高吧。现在这个简化版已经降下来了，成了一个绿题。
题目意思就是说，给你一棵有 n 个节点的树，每个节点上都有一个点权 a_i。现在要求你在树上选择若干条（可以不选，但最多选 k 条）互不相交的链，问最终这若干条链所经过的点的点权之和的和最大是多少，输出这个最大值。
注意到这个 $k$ 特小，~~启发我们乱搞~~。
由于是一棵树，又是统计最大值，而且还是 F 的这个难度，合理猜测正解是树形 DP。~~恭喜你猜对了！~~
当只考虑节点 $u$ 的子树时，针对 $u$ 这个节点只有以下三种情况：
- 选择的链中没有任何一条链包含 $u$ 节点。
- 选择的链中有一条包含了 $u$ 节点，并且 $u$ 节点还是这条链的某个端点。
- 选择的链中有一条包含了 $u$ 节点，但 $u$ 节点并不是这条链中的端点。
分别用 $0 / 1 / 2$ 表示以上三种情况。
那么状态设计就很显然了，$dp_{u,i,j}$ 表示当前考虑 $u$ 的子树，一共选择了 $i$ 条链，并且 $u$ 节点的情况为 $j$。
初始化 $dp_{u,0,0}=0$，$dp_{u,1,1}=dp_{u,1,2}=a_u$，其他均为极小值。
令 $1$ 为根跑 DFS，枚举 $u$ 的儿子 $v$，先往下收集到 $v$ 的信息，再及时进行转移。
转移分以下三种情况：
1. 直接合并类：
- 直接枚举 $u$ 原本的链数 $i$ 以及 $v$ 子树的链数 $j$，然后合并两个即可。需枚举情况，这里让 $u$ 原本情况为 $p$，$v$ 子树情况为 $q$。转移方程 $dp_{u,i+j,p} = \max( dp_{u,i+j,p} , dp_{u,i,p} + dp_{v,j,q} )$。
2. 链上增点类：
- 如果 $v$ 子树中有某条链以 $v$ 为某个端点，那么可以直接让 $u$ 节点加到这条链上。当然了，$u$ 原本底下有的也要算上，不过情况为 $0$。转移后情况是 $1$，因为 $u$ 就成为了新的端点了。转移方程 $dp_{u,i+j,1} = \max( dp_{u,i+j,1} , dp_{u,i,0} + dp_{v,j,1} + a_u )$。
3. 合并两链类：
- 这种类型就是，如果 $u$ 原本就有一条链 $u$ 是端点，$v$ 子树中也有一条链 $v$ 是端点，那么可以借助 $u$ 到 $v$ 的这条边将这两条链合并为一个链进行转移。当然了，合并之前两个的情况都是 $1$，但合并之后 $u$ 可就不是端点了，所以情况是 $2$。转移方程 $dp_{u,i+j-1,2} = \max( dp_{u,i+j-1,2} , dp_{u,i,1} + dp_{v,j,1} )$。
转移时为避免重复转移这一条链，可以先开一个 $tmp$ 暂存下答案，这一轮全部转移完成后再对 $dp$ 数组进行更新。
最终答案 $ans$ 为 $\max\{dp_{1,i,j}\}$，其中 $i$ 从 $0 \sim k$ 而 $j$ 从 $0 \sim 2$。
时间复杂度 $O(n \times k^2)$。由于情况数的表示，时间复杂度中还拥有 $9$ 的常数。
最后给各位贴上~~经过无限次压行后变得~~很短的代码！
```cpp
#include<bits/stdc++.h>
#define LL long long
#define pb push_back
using namespace std;
const int N = 2e5+5;vector<int> g[N];
LL n,k,a[N],dp[N][10][5],tmp[10][5],ans;
void change(int u,int v){
memset(tmp,-0x3f,sizeof(tmp));
for(int i=0;i<=k;i++)for(int j=0;j<=k;j++){
if(i+j<=k)for(int p=0;p<3;p++)for(int q=0;q<3;q++)
tmp[i+j][p]=max(tmp[i+j][p],dp[u][i][p]+dp[v][j][q]);
if(i+j<=k)tmp[i+j][1]=max(tmp[i+j][1],dp[u][i][0]+dp[v][j][1]+a[u]);
if(i+j>0&&i+j-1<=k)tmp[i+j-1][2]=max(tmp[i+j-1][2],dp[u][i][1]+dp[v][j][1]);
}
for(int i=0;i<=k;i++)for(int j=0;j<3;j++)
dp[u][i][j]=max(dp[u][i][j],tmp[i][j]);return;
}
void DFS(int u,int fa){
dp[u][0][0]=0,dp[u][1][1]=a[u],dp[u][1][2]=a[u];
for(int v:g[u])if(v^fa)DFS(v,u),change(u,v);return;
}
int main(){
cin>>n>>k;for(int i=1;i<=n;i++)cin>>a[i];
for(int i=1;i<n;i++){int x,y;cin>>x>>y;g[x].pb(y),g[y].pb(x);}
memset(dp,-0x3f,sizeof(dp));DFS(1,0);ans=-0x3f3f3f3f3f3f3f3f;
for(int i=0;i<=k;i++)for(int j=0;j<3;j++)ans=max(ans,dp[1][i][j]);cout<<ans<<"\n";
return 0;
}
```
如果本篇题解对你有帮助的话，麻烦点一个小小的赞，真是太感谢啦！