curimit知道陶陶很喜欢吃苹果。于是curimit准备在陶陶生日的时候送给他一棵苹果树。
curimit准备了一棵这样的苹果树作为生日礼物：这棵苹果树有n个节点，每个节点上有c[i]个苹果，这棵树高度为h。
可是，当curimit把这棵树给陶陶看的时候，陶陶却说：“今年生日不收礼，收礼只收节点数减高度不超过k的苹果树。”这下curimit犯难了，curimit送来的树枝繁叶茂，不满足节点数-高度≤k。于是curimit决定剪掉一些枝条，使得修剪过后的树满足节点数-高度≤k，但是curimit又想保留尽量多的苹果数目。curimit想请你帮他算算经过修剪后的树最多能保留多少个苹果。
注：
一， 节点1为树根，不能把它剪掉。
二， 1个节点的树高度为1。
Input输入文件的第一行为两个整数n，k分别表示这棵树有n个节点，修剪后的树节点数-高度≤k。
第二行开始到第n+1行，每行有两个数，第i+1行的两个数father[i]和c[i]分别表示节点i的父亲是father[i]和节点i处有c[i]个苹果。
规定：节点1的父亲为0。
Output输出文件仅包含一行，ans，表示在满足修建后的树节点数-高度≤k的条件下，最多能保留多少个苹果。
Hint对于100%的数据，n≤4000 0≤k≤=500
Solution翻译一下题目，就是让你选一条链，然后再选 \(k\) 个点，使得这一条链上的点权加上选出来的点权和最大。
显然树形 \(dp\) 。
观察到以下性质：选出来的链，一定是从根节点到叶子节点的某条链。如果不这样选，总能找到更优的选法使总答案变大。
所以对于树上每条到叶子的链，通过树形 \(dp\) 找出以这条链为界限向左和向右选 \(j\) 个点能获得的最大收益，那么最后答案就是 \(\max \limits_{sons[i]=0}(sum[i]+\max\limits_{0\leq j\leq k}f[i][j]+g[i][k-j])\)。
这个 \(f\) 数组怎么求呢？
在 \(dfs\) 的过程中，搜完一条链并回溯之后方可继续搜下一条链。那么在搜当前链的过程中，根节点里存的信息实际上是上一条完整的链的信息，即 \(f[1][j]\) 表示当前这条链左边所有点中选 \(j\) 个的最大点权和，于是我们就从一号点一路将这个 \(f\) 数组放进叶子节点，然后再从叶子节点向上更新选当前这条链上某个点的最大价值，这就求完了 \(f\) 数组。 \(g\) 数组也是同理。
最后按照上面的公式更新即可。
#include<cstdio> #include<cctype> #define N 4005 #define max(A,B) ((A)>(B)?(A):(B)) #define min(A,B) ((A)<(B)?(A):(B)) int val[N]; int deg[N]; int sum[N]; int cnt,n,m; int f[N][505]; int g[N][505]; int son[N][N]; int getint() { int x=0;char ch=getchar(); while(!isdigit(ch)) ch=getchar(); while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return x; } void dfs1(int now){ sum[now]+=val[now]; for(int i=1;i<=son[now][0];i++){ int to=son[now][i]; for(int j=0;j<=m;j++) f[to][j]=f[now][j]; sum[to]=sum[now]; dfs1(to); for(int j=1;j<=m;j++) f[now][j]=max(f[now][j],f[to][j-1]+val[to]); } } void dfs2(int now){ for(int i=son[now][0];i;i--){ int to=son[now][i]; for(int j=0;j<=m;j++) g[to][j]=g[now][j]; dfs2(to); for(int j=1;j<=m;j++) g[now][j]=max(g[now][j],g[to][j-1]+val[to]); } } signed main() { n=getint(),m=getint(); for(int i=1;i<=n;i++) { if(i==1){ getint(),val[1]=getint(); continue; } else { int a=getint(); son[a][++son[a][0]]=i; val[i]=getint(); } } dfs1(1); dfs2(1); int ans=0; for(int i=1;i<=n;i++){ if(son[i][0]) continue; for(int j=0;j<=m;j++) ans=max(ans,f[i][j]+g[i][m-j]+sum[i]); } printf("%d\n",ans); return 0; }