Binary Apple Tree

题目链接：http://acm.hust.edu.cn:8080/judge/contest/viewProblem.action?pid=46506

http://acm.timus.ru/problem.aspx?space=1&num=1018

#include <stdio.h>
#include <string.h>

//using namespace std;

struct Tree{
	int l,r;//左右孩子的下标
	int s;//苹果的个数
};

//题意：一棵苹果树上面由很多枝，每个枝上都有很多苹果，现在要剪枝，题目中告诉你剪完之后保留枝的数目q
//      问保留q枝时能保留苹果个数的最大值

//类型：树形DP

int num[101][101];//存各个枝上的苹果树 枝的两顶点i、j
bool vis[101];//访问记录
int dp[101][101];//dp[i][j]以第i个顶点为根保留j条边的苹果树
Tree tree[101];//根据输入数据建立的树  用dfs进行建树
int n,q,x,y,c;

void dfs(int x){
	vis[x]=true;
	for(int i=1;i<=n;i++){
		if(!vis[i] && num[x][i]!=-1){
			if(tree[x].l==0)tree[x].l=i;//for循环找出其相连点 至于作为哪个孩子无所谓哪一个空着就放哪个就行
		    else tree[x].r=i;
		    tree[i].s=num[x][i];//将枝上的苹果向远离跟的那边放
		    dfs(i);//递归的建树
		}
	}
}

int fun_dp(int t,int k){
	if(dp[t][k]!=-1)return dp[t][k];//相当于向根的方向找 而根的方向已经确定最优值 直接返回即可
	if(t==0 || k==0){//如果t=0说明已经是叶节点直接置零返回即可  如果k=0说明以它为根的节点只保留零条边 所以也直接置零就可以
		dp[t][k]=0;
		return dp[t][k];
	}
	dp[t][k]=0;
	for(int i=0;i<k;i++){
		int ls=fun_dp(tree[t].l,i);
		int rs=fun_dp(tree[t].r,k-1-i);
		if(dp[t][k]<ls+rs)dp[t][k]=ls+rs;
	}
	dp[t][k]+=tree[t].s;
	return dp[t][k];
}

int main(){
	scanf("%d%d",&n,&q);
	memset(num,-1,sizeof(num));
	for(int i=0;i<n-1;i++){
		scanf("%d%d%d",&x,&y,&c);
		num[x][y]=c;
		num[y][x]=c;
	}
	memset(vis,false,sizeof(vis));
	memset(tree,0,sizeof(tree));
	dfs(1);
	memset(dp,-1,sizeof(dp));
	printf("%d",fun_dp(1,q+1));
	return 0;
}