P2015 二叉苹果树
题目大意：有一棵二叉树性质的苹果树，每一根树枝上都有着一些苹果，现在要去掉一些树枝，只留下q根树枝，要求保留最多的苹果数（去掉树枝后不一定是二叉树）
思路：一开始就很直接的想到树形dp上了，因为就是每个树枝要与不要的问题，但要找到如何找到一个转移方程呢，首先我们想一下，最后保留的是一棵树，所以肯定是从根节点开始，然后在它的两个子节点中向下延伸不停的选择保留树枝，换句话说，假如需要保留q根树枝，我们已经知道了根节点的两个子节点保留任意根数的最多苹果数，那么根节点要保留q根树枝的状态，就是遍历一下其中一个根节点保留i根树枝，然后另一个根节点保留q-i根树枝，不停更新答案，转换成转移方程便是：
dp[u][q]=max(dp[u][q],dp[v1][i]+dp[v2][q-i]) （dp[i][j]就代表i节点保留j根树枝的最大苹果数）
不过需要考虑到的是，根节点没有入度，但其他节点有入度，以及当前节点在它的子树的树枝数，也就是：
dp[u][q]=max(dp[u][q],dp[v1][i]+dp[v2][q-i-g]+c) （g就是它的入度，根节点是0，其他都是1，而c就是父节点和它连接的那根树枝的苹果数）
1 #include<cstdio> 2 #include<cstring> 3 const int N=118; 4 struct Side{ 5 int to,ne,val; 6 }S[2*N];//前向星存边 7 int sn,head[N],dp[N][N]={0}; 8 int max(int a,int b){ 9 return a>b ? a : b; 10 } 11 void add(int u,int v,int c) 12 { 13 S[sn].to=v; 14 S[sn].val=c; 15 S[sn].ne=head[u]; 16 head[u]=sn++; 17 } 18 int treed(int u,int f,int c,int g)//当前节点，父节点，父节点与它相连树枝上的苹果数 19 { 20 int v[3]={0},du[3]={0},s=0;//分别保留两个编号以及总树枝数 21 for(int i=head[u];i!=-1;i=S[i].ne) 22 { 23 if(S[i].to!=f) 24 { 25 v[s]=S[i].to; 26 du[s]=treed(v[s],u,S[i].val,1); 27 s++; 28 } 29 } 30 for(int i=1;i<=du[0]+du[1]+g;i++)//du[0]+du[1]+g就是这个节点为根节点最多能保留的树枝数 31 { 32 for(int j=max(0,i-du[1]-g);j<=du[0]&&j<=i-g;j++) 33 dp[u][i]=max(dp[u][i],dp[v[0]][j]+dp[v[1]][i-j-g]+c); 34 } 35 return du[0]+du[1]+g; 36 } 37 int main() 38 { 39 int n,q,u,v,c; 40 memset(head,-1,sizeof(head)); 41 scanf("%d%d",&n,&q); 42 for(int i=1;i<n;i++) 43 { 44 scanf("%d%d%d",&u,&v,&c); 45 add(u,v,c);//没有严格给出方向，建双向边 46 add(v,u,c); 47 } 48 treed(1,1,0,0); 49 printf("%d ",dp[1][q]); 50 return 0; 51 }