【题解】二叉苹果树

(Question)

题目大意：边权版本树形(dp),求保留(Q)条边，使得其边权和最大。当然，必须联通。（要不就不是(dp)了)

那考虑设计(dp[i][j])表示第(i)个节点，选择(j)条边的最佳方案。

写出方程为：

[dp[i][j]=max_{vin son[i]}dp[i][j-k]+dp[v][k]+e[i].dis ]

枚举(k)表示边数。

这有一个显然问题：求出的不一定联通啊。

于是我们把(i->son[i])的一条边单独留出来，就有：

[dp[i][j]=max_{vin son[i]}dp[i][j-k-1]+dp[v][k]+e[i].dis ]

这题做完了。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1000;
int n,q,tot,dp[MAXN][MAXN];
int head[MAXN<<1],siz[MAXN];
struct edge{
	int nxt,to,dis;
}e[MAXN<<1];
inline void add(int x,int y,int w){
	e[++tot].to=y;
	e[tot].nxt=head[x];
	e[tot].dis=w;
	head[x]=tot;
}
void dfs(int x,int fa){
	for(int i=head[x];i;i=e[i].nxt){
		int j=e[i].to;if(j==fa)continue;
		dfs(j,x);siz[x]+=siz[j]+1;
		for(int l=min(siz[x],q);l>=0;--l){
			for(int k=min(l-1,siz[j]);k>=0;--k)
				dp[x][l]=max(dp[x][l],dp[j][k]+dp[x][l-k-1]+e[i].dis);
		}
	}
}
int main(){
	scanf("%d%d",&n,&q);
	for(int i=1;i<n;++i){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		add(x,y,z);add(y,x,z);
	}
	dfs(1,0);
	int ans=-1;
	
	printf("%d
",dp[1][q]);
	return 0;
}