BZOJ_4987_Tree_树形DP

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;
#define N 3050
#define _min(x,y) ((x)<(y)?(x):(y))
int head[N],to[N<<1],nxt[N<<1],val[N<<1],n,cnt,K,f[N][N][3],a[N];
int ans=1<<30,siz[N];
inline void add(int u,int v,int w) {
	to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt; val[cnt]=w;
}
void upd(int &x,int y) {if(x>y) x=y;}
void dp(int x,int y) {
	int i,j,k; siz[x]=1;
	f[x][1][0]=f[x][1][1]=0;
	for(i=head[x];i;i=nxt[i]) {
		if(to[i]!=y) {
			dp(to[i],x);
			for(j=siz[x];j;j--) {
				for(k=siz[to[i]];k;k--) {
					int w=val[i],w2=w<<1;
					upd(f[x][j+k][0],f[x][j][0]+f[to[i]][k][0]+w2);
					upd(f[x][j+k][1],f[x][j][0]+f[to[i]][k][1]+w);
					upd(f[x][j+k][1],f[x][j][1]+f[to[i]][k][0]+w2);
					upd(f[x][j+k][2],f[x][j][0]+f[to[i]][k][2]+w2);
					upd(f[x][j+k][2],f[x][j][1]+f[to[i]][k][1]+w);
					upd(f[x][j+k][2],f[x][j][2]+f[to[i]][k][0]+w2);
				}
			}
			siz[x]+=siz[to[i]];
		}
	}
	ans=min(ans,f[x][K][2]);
}
int main() {
	memset(f,0x3f,sizeof(f));
	scanf("%d%d",&n,&K);
	int i,x,y,z;
	for(i=1;i<n;i++) {
		scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z);
	}
	dp(1,0);
	printf("%d\n",ans);
}