5565 二叉苹果树

 时间限制: 1 s

 空间限制: 128000 KB

 题目等级 : 黄金 Gold

 

题目描述 Description

      有一棵苹果树，如果树枝有分叉，一定是分2叉（就是说没有只有1个儿子的结点）这棵树共有N个结点（叶子点或者树枝分叉点），编号为1-N,树根编号一定是1。我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。

       给定需要保留的树枝数量，求出最多能留住多少苹果。

 

输入描述 Input Description

    第1行2个数，N和Q(1<=Q<= N,1<N<=100)。

   N表示树的结点数，Q表示要保留的树枝数量。接下来N-1行描述树枝的信息。

每行3个整数，前两个是它连接的结点的编号。第3个数是这根树枝上苹果的数量。

每根树枝上的苹果不超过30000个。

 

输出描述 Output Description

剩余苹果的最大数量。

 

样例输入 Sample Input

5 2

1 3 1

1 4 10

2 3 20

3 5 20

 

样例输出 Sample Output

21

 

数据范围及提示 Data Size & Hint

对于20%数据 n<=20;

对于100%数据1<N<=100,1<=Q<= N.

 --------------------------------------------------------------------------------------------------------------------------------------------

很简单的一道树形DP，思路是 先把二叉树各边边权值转移到子节点上（这么做才能确定各点的状态），这样点x的状态即 点x的子树（包括点x）上保留y个点所得的最大值，开二维数组储存状态即dp[x][y]，然后一遍DFS确定dp[x][1]的值，即等于点x的权值，然后在回溯时进行状态转移，不难得出状态转移方程为：

dp[x][i]=max(dp[l[x]][j]+dp[r[x]][i-j-1]+dp[x][1],dp[x][i])。但要注意的问题是，最后还要对根节点进行一次状态转移：dp[1][Q]=max(dp[l[1]][i]+dp[r[1]][Q-i],dp[1][Q])，因为点权之前是由边权转移而来，而根节点没有参与边权的转移，故需要分开来。AC代码：

1 #include
      
        2 #include
       
         3 #define maxn 233 4 struct node{ 5     int to,next,w; 6 }; 7 node e[maxn]; 8 int N,Q,dp[maxn][maxn],pre[maxn],cnt,l[maxn],r[maxn]; 9 bool vis[maxn];10 int read();11 int max(int,int);12 void dfs(int);13 void build(int,int,int);14 int main(){15     memset(dp,0,sizeof(dp));16     memset(vis,0,sizeof(vis));17     memset(dp,0,sizeof(dp));18     N=read();Q=read();cnt=0;19     for(int i=1;i
        
         c||c>'9'){
    if(c=='-')f=-1;c=getchar();}32     while('0'<=c&&c<='9')ans=ans*10+c-48,c=getchar();return ans*f;33 }34 void build(int x,int y,int z){35     e[++cnt].to=y;e[cnt].next=pre[x];pre[x]=cnt;e[cnt].w=z;36     e[++cnt].to=x;e[cnt].next=pre[y];pre[y]=cnt;e[cnt].w=z;37 }38 void dfs(int x){39     if(!vis[x]){40         vis[x]=1;41         bool po=1;42         for(int i=pre[x];i;i=e[i].next){43             int to=e[i].to;44             if(!vis[to]){45                 dp[to][1]=e[i].w;46                 if(po)l[x]=to,po=0;47                 else r[x]=to; 48             }49             dfs(to);50         }51         for(int i=2;i<=Q;i++)52             for(int j=0;j
         
          y?x:y;58 }
         
        
       
      

其实自己还有一个思路，就是把状态定为 x点的子树中保留y条边时的最大值，这样就可以只有一条状态转移方程，但个人觉得处理起来没有第一种思路好。