Description

给一棵n 个结点的有根树，结点由1 到n 标号，根结点的标号为1。每个结点上有一个物品，第i 个结点上的物品价值为vi。
你需要从所有结点中选出若干个结点，使得对于任意一个被选中的结点，其到根的路径上所有的点都被选中，并且选中结点的个数不能超过给定的上限lim。在此前提下，你需要最大化选中结点上物品的价值之和。
求这个最大的价值之和。

Solution

一道很显然的树形DP，但分析复杂度发现为$O(n^3)$，过不了。
这是优化一下：
每次往下走的时候，把当前点的信息下传，下面做完以后再传上来，

复杂度：$O(n^2)$

Code

Code From CTY:

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a) for(int i=last[a];i;i=next[i])
#define N 3005
using namespace std;
int n,k,x,y,l,v[N],f[N][N];
int last[N],next[N*2],t[N*2];
void add(int x,int y) {t[++l]=y;next[l]=last[x];last[x]=l;
}
void dfs(int x,int y) {rep(i,x) if (t[i]!=y) {fo(j,0,k-1) f[t[i]][j]=f[x][j]+v[t[i]];dfs(t[i],x);fo(j,1,k) f[x][j]=max(f[x][j],f[t[i]][j-1]);}
}
int main() {freopen("tree.in","r",stdin);freopen("tree.out","w",stdout);scanf("%d%d",&n,&k);fo(i,1,n) scanf("%d",&v[i]);fo(i,1,n-1) scanf("%d%d",&x,&y),add(x,y),add(y,x);dfs(1,0);printf("%d",f[1][k-1]+v[1]);
}