树形DP--zoj_3506

        http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3506

        题目大意为给定一颗节点带权值的树，和整数k，要求给出一个策略，对这棵树切k刀（对边切，切完保留一部分，丢弃一部分），最后得到的部分的权值和为最大/最小。

        f[i][j]为以第i个节点为根，切k刀所得到的最小值。普通dp的想法就是对于某一个节点，如果它为根并保留到最后，那么就在所有的边N中选取k条边，共有C(N,k)种情况，遍历每种情况更新f[i][k].显然这种方法效率是指数级的，会TLE。

        那么如果以节点i为根递归的遍历i的子节点，来更新f[i][0],f[i][1]...f[i][k]，就可以在1个DFS的时间内完成整个DP过程。因此有一下思路，对于节点i的子节点j，考虑3中情况

1）子节点j对应的子树保留，但是子树切1---m刀，节点i对应的树切m-1---0刀。3）子节点j对应的树不保留（也就是说子节点j对应的树至少切1刀）

情况1:f[i][j]=min(f[i][j],f[i][j-m]+f[j][k-m])

情况2:f[i][j]=min(f[i][j],f[i][k-m])(m=1----k)

        注意1：在更新子节点j之前应该先将f[i][m]初始化f[i][m]+=f[j][0];       

        注意2：在更新f[i][0]----f[i][k]的过程中一定要逆序更新，因为在更新f[i][j]的时候所用到的子结构f[i][0]---f[i][j-1]应该是上一个子节点更新之后的。如

        注意3：最后的结果也是递归的查找，如果根节点1不再最后的结果中，那么递归的遍历他的子节点，对于子节点j，遍历f[j][p]，其中p的取值应该是max(0,k-除j子树之外的所有边树)---j子树中的所有边数

      

#include<string> 
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<string.h>
using namespace std;   
const int maxn=1005;
const int inf=99999999;
int fir[maxn],next2[maxn*2],to[maxn*2];
int num[maxn];
int n,m;
int f[maxn][22];
int value[maxn];
int edgenum;
vector<int>v[maxn]; 
void add_edge(int u,int v)
{
 next2[edgenum]=fir[u];
 fir[u]=edgenum;
 to[edgenum]=v;
 edgenum++;
  
}
void dfs(int u,int fa)
{
 int size=v[u].size();
 for(int i=0;i<size;i++)if(v[u][i]!=fa)
 {
  add_edge(u,v[u][i]);
  dfs(v[u][i],u);
 }
}
void solve(int u,int p)
{
 num[u]=1;
 f[u][0]=value[u];
 for(int j=1;j<=m;j++)f[u][j]=inf;
 f[u][0]=0;
 for(int e=fir[u];e!=-1;e=next2[e])
if(to[e]!=p)
 {
  int v=to[e];
  solve(v,u);
  num[u]+=num[v];
  for(int j=m;j>=0;j--)
  {
   f[u][j]+=f[v][0]; //!!注意1
    for(int k=0;k<j;k++)//k!=j 注意2
   {
    f[u][j]=min(f[u][j],f[u][k]+f[v][j-k]);
   } 
   for(int k=1;k<=j&&k<=num[v];k++)
   {
    f[u][j]=min(f[u][j],f[u][j-k]);
   }
   } 
 }
 for(int j=0;j<=m;j++)f[u][j]+=value[u];
 }
int DP()
{
 int ans=inf;
 solve(1,-1);
 ans=min(ans,f[1][m]);
 if(m>0){
  for(int i=2;i<=n;i++)
   for(int j=max(m+num[i]-num[1],0);j<num[i]&&j<m;j++)//!注意3
    ans=min(ans,f[i][j]);
 }
 return ans;
} 
int main()
{
freopen("e:\\zoj\\zoj_3506.txt","r",stdin); 
while(scanf("%d%d",&n,&m)==2)
 {
  for(int i=1;i<=n;i++)scanf("%d",&value[i]);
  memset(fir,-1,sizeof(fir));
  for(int i=1;i<=n;i++)v[i].clear();
  edgenum=0;
  for(int i=1;i<n;i++)
  {
   int a,b;
   scanf("%d%d",&a,&b);
   v[a].push_back(b);
   v[b].push_back(a);
  }
  dfs(1,-1);
  for(int i=1;i<=n;i++)
   for(int j=1;j<=m;j++)f[i][j]=inf; 
  memset(num,0,sizeof(num));
  printf("%d ",DP());
  for(int i=1;i<=n;i++)value[i]=-value[i];
  for(int i=1;i<=n;i++)
   for(int j=0;j<=m;j++)f[i][j]=inf; 
  memset(num,0,sizeof(num));    
  printf("%d\n",-DP());
 }
}