http://acm.timus.ru/problem.aspx?space=1&num=1018
题意：
有一棵苹果树，苹果树的是一棵二叉树，共N个节点，树节点编号为1~N，编号为1的节点为树根，边可理解为树的分枝，每个分支都长着若干个苹果，现在要要求减去若干个分支，保留M个分支，要求这M个分支的苹果数量最多。
树dp跟一般的dp的解决方案一样也是三个步骤：1、确定状态；2、状态转移；3、算法实现。（算法的实现要满足无后效性等基本原则）
由于树的结构，使用记忆化搜索比较容易实现。
题目分析：设dp[u][q]为由第u个节点往下取q个分支的最优值，则当前节点的dp值来源于其子节点，这里就要有子节点的个数进行分类讨论。
当子节点数为1时，就只能沿该路径走下去,dp[u][q] = dp[child][q-1] + maz[u][child];
当子节点数为2时，dp[u][q] = max{dp[child1][k]+maz[u][child1] + dp[child2][q-k-2] + maz[u][child2]}或者像节点数为1的情况一样只来源于其中一个子节点。
View Code
1 /* 2 Author:Zhaofa Fang 3 Lang:C++ 4 */ 5 #include <cstdio> 6 #include <cstdlib> 7 #include <sstream> 8 #include <iostream> 9 #include <cmath> 10 #include <cstring> 11 #include <algorithm> 12 #include <string> 13 #include <utility> 14 #include <vector> 15 #include <queue> 16 #include <stack> 17 #include <map> 18 #include <set> 19 using namespace std; 20 21 typedef long long ll; 22 #define DEBUG(x) cout<< #x << ':' << x << endl 23 #define REP(i,n) for(int i=0;i < (n);i++) 24 #define REPD(i,n) for(int i=(n-1);i >= 0;i--) 25 #define FOR(i,s,t) for(int i = (s);i <= (t);i++) 26 #define FORD(i,s,t) for(int i = (s);i >= (t);i--) 27 #define PII pair<int,int> 28 #define PB push_back 29 #define MP make_pair 30 #define ft first 31 #define sd second 32 #define lowbit(x) (x&(-x)) 33 #define INF (1<<30) 34 35 int dp[110][110],maz[110][110]; 36 vector<int>vec[110]; 37 38 int dfs(int u,int q,int f){ 39 if(vec[u].size()==0 || (vec[u].size()==1&&f!=-1) || q<=0){ 40 return 0; 41 } 42 if(!dp[u][q]){ 43 int tmp = 0; 44 if((vec[u].size()==2 && f!=-1) || (vec[u].size()==1 && f==-1)){ 45 int v = vec[u][0]; 46 if(v == f)v = vec[u][1]; 47 tmp = dfs(v,q-1,u) + maz[u][v]; 48 } 49 else { 50 int v[3]={0};int nn = 0; 51 REP(i,vec[u].size()){ 52 if(vec[u][i] != f)v[nn++] = vec[u][i]; 53 } 54 FOR(i,0,q-2){ 55 int cnt = dfs(v[0],i,u) + maz[u][v[0]]; 56 cnt += dfs(v[1],q-i-2,u) + maz[u][v[1]]; 57 tmp = max(tmp,cnt); 58 } 59 tmp = max(tmp,dfs(v[0],q-1,u) + maz[u][v[0]]); 60 tmp = max(tmp,dfs(v[1],q-1,u) + maz[u][v[1]]); 61 } 62 dp[u][q] = tmp; 63 } 64 return dp[u][q]; 65 } 66 67 int main(){ 68 //freopen("in","r",stdin); 69 //freopen("out","w",stdout); 70 int n,q; 71 while(~scanf("%d%d",&n,&q)){ 72 memset(dp,0,sizeof(dp)); 73 memset(maz,0,sizeof(maz)); 74 FOR(i,1,n)vec[i].clear(); 75 REP(i,n-1){ 76 int a,b,x; 77 scanf("%d%d%d",&a,&b,&x); 78 maz[a][b] = maz[b][a] = x; 79 vec[a].PB(b);vec[b].PB(a); 80 } 81 int ans = dfs(1,q,-1); 82 printf("%d\n",ans); 83 } 84 return 0; 85 }