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就是父节点和它连接的那根树枝的苹果数）
#include<cstdio>
#include<cstring>
const int N=;
struct Side{
int to,ne,val;
}S[*N];//前向星存边
int sn,head[N],dp[N][N]={};
int max(int a,int b){
return a>b ? a : b;
}
void add(int u,int v,int c)
{
S[sn].to=v;
S[sn].val=c;
S[sn].ne=head[u];
head[u]=sn++;
}
int treed(int u,int f,int c,int g)//当前节点，父节点，父节点与它相连树枝上的苹果数
{
int v[]={},du[]={},s=;//分别保留两个编号以及总树枝数
for(int i=head[u];i!=-;i=S[i].ne)
{
if(S[i].to!=f)
{
v[s]=S[i].to;
du[s]=treed(v[s],u,S[i].val,);
s++;
}
}
for(int i=;i<=du[]+du[]+g;i++)//du[0]+du[1]+g就是这个节点为根节点最多能保留的树枝数
{
for(int j=max(,i-du[]-g);j<=du[]&&j<=i-g;j++)
dp[u][i]=max(dp[u][i],dp[v[]][j]+dp[v[]][i-j-g]+c);
}
return du[]+du[]+g;
}
int main()
{
int n,q,u,v,c;
memset(head,-,sizeof(head));
scanf("%d%d",&n,&q);
for(int i=;i<n;i++)
{
scanf("%d%d%d",&u,&v,&c);
add(u,v,c);//没有严格给出方向，建双向边
add(v,u,c);
}
treed(,,,);
printf("%d\n",dp[][q]);
return ;
}
代码千万条，自觉第一条，复制粘贴爽，打铁泪两行