URAL 1018 Binary Apple Tree 树形DP 好题经典

浏览数：70 / 时间：2015年06月11日

1018. Binary Apple Tree

Time limit: 1.0 second
Memory limit: 64 MB

Let‘s imagine how apple tree looks in binary computer world. You‘re right, it looks just like a binary tree, i.e. any biparous branch splits up to exactly two new branches. We will enumerate by integers the root of binary apple tree, points of branching and the ends of twigs. This way we may distinguish different branches by their ending points. We will assume that root of tree always is numbered by 1 and all numbers used for enumerating are numbered in range from 1 to N, where N is the total number of all enumerated points. For instance in the picture below N is equal to 5. Here is an example of an enumerated tree with four branches:

As you may know it‘s not convenient to pick an apples from a tree when there are too much of branches. That‘s why some of them should be removed from a tree. But you are interested in removing branches in the way of minimal loss of apples. So your are given amounts of apples on a branches and amount of branches that should be preserved. Your task is to determine how many apples can remain on a tree after removing of excessive branches.

Input

First line of input contains two numbers: N and Q (2 ≤ N ≤ 100; 1 ≤ Q ≤ N − 1). N denotes the number of enumerated points in a tree. Q denotes amount of branches that should be preserved. NextN − 1 lines contains descriptions of branches. Each description consists of a three integer numbers divided by spaces. The first two of them define branch by it‘s ending points. The third number defines the number of apples on this branch. You may assume that no branch contains more than 30000 apples.

Output

Output should contain the only number — amount of apples that can be preserved. And don‘t forget to preserve tree‘s root ;-)

Sample

input	output
5 2 1 3 1 1 4 10 2 3 20 3 5 20	21

树形DP第一题，经典题

某一位大神说，经典题都要自己做，不能看题解，因为做一题少一题

这道题从昨晚11点到1点，然后今天12：30继续想到2:00，终于AC了，挺开心的。

题意：给出一颗二叉树，有n个节点，编号为1~n，1是根节点。

树上的每一条边挂有一些苹果（为什么不是在节点挂苹果），然后问你只保留k条边的情况下，最多能保留多少个苹果。

昨晚想的是用优先队列，知道了保留的边数，就知道了要去掉的边数。递归处理树，把每一条边的权值放到2个节点中深度较大的那一个节点，然后递归处理，每一个节点的权值变为以这个节点为根的子树的权值的和，包括本身的权值。

然后每次把叶子节点放入优先队列中，每输出一个节点，要去掉的边就-1，然后把这个节点的父亲节点的权值更新后加入优先队列。直到要去掉的边为0.

然而，这样是错的。

无法保证最优。

乖乖树形DP.

dp[i][j]表示以i为根的子树保留j个顶点时的最大的苹果树。

然后递归处理后，自底向上递归求解。

分别考虑没有子树，只有左子树，左右子树都有的情况。

注意：根据处理，有右子树就一定有左子树。

  1 #include<cstdio>
  2 #include<cstring>
  3 #include<algorithm>
  4 
  5 using namespace std;
  6 
  7 const int maxn=110;
  8 int dp[maxn][maxn];
  9 int ls[maxn];
 10 int rs[maxn];
 11 int w[maxn];                //节点的权值
 12 int siz[maxn];              //以之为根的子树的节点个数
 13 int dep[maxn];              
 14 int e[maxn][3];             //保存2个节点和权值
 15 struct Edge
 16 {
 17     int to,next;
 18 }edge[maxn<<1];
 19 
 20 int head[maxn];
 21 int tot;
 22 int n,k;
 23 
 24 void init()
 25 {
 26     memset(head,-1,sizeof(head));
 27     tot=1;
 28     memset(ls,-1,sizeof(ls));
 29     memset(rs,-1,sizeof(rs));
 30     memset(dep,-1,sizeof(dep));
 31     memset(siz,0,sizeof(siz));
 32     memset(dp,-1,sizeof(dp));
 33 }
 34 
 35 void addedge(int u,int v)
 36 {
 37     edge[tot].to=v;
 38     edge[tot].next=head[u];
 39     head[u]=tot++;
 40 }
 41 
 42 void dfs1(int u,int d)
 43 {
 44     siz[u]=1;
 45     dep[u]=d;
 46     for(int i=head[u];~i;i=edge[i].next)
 47     {
 48         int v=edge[i].to;
 49         if(dep[v]<0)
 50         {
 51             dfs1(v,d+1);
 52             siz[u]+=siz[v];
 53         }
 54     }
 55 }
 56 
 57 void dfs2(int u)
 58 {
 59     if(siz[u]<=1)
 60         return ;
 61     for(int i=head[u];~i;i=edge[i].next)
 62     {
 63         int v=edge[i].to;
 64         if(dep[v]<dep[u])
 65             continue;
 66         if(ls[u]==-1)
 67         {
 68             ls[u]=v;
 69             dfs2(v);
 70         }
 71         else
 72         {
 73             rs[u]=v;
 74             dfs2(v);
 75         }
 76     }
 77 }
 78 
 79 void tree_dp(int u)
 80 {
 81     if(ls[u]==-1&&rs[u]==-1)
 82     {
 83         dp[u][0]=0;
 84         dp[u][1]=w[u];
 85     }
 86     else if(ls[u]!=-1&&rs[u]==-1)
 87     {
 88         dp[u][0]=0;
 89         tree_dp(ls[u]);
 90         for(int j=1;j<=siz[u];j++)
 91         {
 92             for(int k=0;k<=siz[ls[u]];k++)
 93             {
 94                 dp[u][j]=max(dp[u][j],dp[ls[u]][j-1]+w[u]);
 95             }
 96         }
 97     }
 98     else
 99     {
100         dp[u][0]=0;
101         tree_dp(ls[u]);
102         tree_dp(rs[u]);
103         for(int j=1;j<=siz[u];j++)
104         {
105             for(int k=0;k<=siz[ls[u]];k++)
106             {
107                 int tmp=j-k-1;
108                 if(tmp>=0&&tmp<=siz[rs[u]])
109                 {
110                     dp[u][j]=max(dp[u][j],dp[ls[u]][k]+dp[rs[u]][tmp]+w[u]);
111                 }
112             }
113         }
114     }
115 }
116 
117 int main()
118 {
119     while(scanf("%d%d",&n,&k)!=EOF)
120     {
121         init();
122         for(int i=1;i<n;i++)
123         {
124             scanf("%d%d%d",&e[i][0],&e[i][1],&e[i][2]);
125             addedge(e[i][0],e[i][1]);
126             addedge(e[i][1],e[i][0]);
127         }
128 
129         if(k>n-1)
130         {
131             k=n-1;                  //注意这里
132         }
133 
134         dfs1(1,1);                      //求出siz,dep
135                                         //给深度大的节点加上权值
136         for(int i=1;i<n;i++)    
137         {
138             if(dep[e[i][0]]>dep[e[i][1]])
139                 swap(e[i][0],e[i][1]);
140             w[e[i][1]]=e[i][2];
141         }
142 
143         dfs2(1);                           //求出左二子和右儿子
144 
145         tree_dp(1);                         
146 
147         printf("%d\n",dp[1][k+1]);          //保留k条边就有k+1个节点
148 
149     }
150     return 0;
151 }