洛谷P2015 二叉苹果树 很明显的一道树形dp。
需要保留的枝条有q条，所以就要保留j=q+1个节点，我们可以分三种情况讨论：
1、树根的左子树为空，只保留右子树，这时右子树保留j-1个节点。
2、树根的右子树为空，只保留左子树，这时左子树保留j-1个节点。
3、左右子树都非空，设左子树保留k个节点，那么右子树保留j-1-k个节点。
设树根为i，左子树为l[i],右子树为r[i],则状态转移方程为：
f[i][j]=max(f[i][j],f(l[i],j)+f(r[i],j-1-k)+a[i]);
附上代码
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<string> 5 #include<cstring> 6 using namespace std; 7 int n,q; 8 int a[105]; 9 int ju[105][105]; 10 int f[105][105]; 11 int r[105]; 12 int l[105]; 13 int aa,bb,cc; 14 inline int dp(int x,int y)//树形dp 15 { 16 if(y==0) return 0; 17 if(r[x]==0&&l[x]==0) return a[x]; 18 if(f[x][y]!=0) return f[x][y]; 19 for(int k=0;k<=y-1;k++) 20 { 21 f[x][y]=max(f[x][y],dp(l[x],k)+dp(r[x],y-1-k)+a[x]);//状态转移 22 } 23 return f[x][y]; 24 } 25 inline void maketree(int v)//建树 26 { 27 for(int i=1;i<=n;i++)//左子树 28 { 29 if(ju[i][v]>=0) 30 { 31 l[v]=i;a[i]=ju[i][v]; 32 ju[i][v]=ju[v][i]=-1; 33 maketree(i); 34 break; 35 } 36 } 37 for(int i=1;i<=n;i++)//右子树 38 { 39 if(ju[i][v]>=0) 40 { 41 r[v]=i;a[i]=ju[v][i]; 42 ju[v][i]=ju[i][v]=-1; 43 maketree(i); 44 break; 45 } 46 } 47 } 48 int main() 49 { 50 cin>>n>>q;q++; 51 for(int i=1;i<=n;i++) 52 for(int j=1;j<=n;j++) 53 ju[i][j]=-1; 54 for(int i=1;i<=n-1;i++) 55 { 56 scanf("%d%d%d",&aa,&bb,&cc); 57 ju[aa][bb]=ju[bb][aa]=cc; 58 } 59 maketree(1);//以1为节点建树 60 printf("%d",dp(1,q)); 61 return 0; 62 }