[DP之树形DP]

树形dp出了应该还是比计数dp要简单的因为很好可以看出来

常用的是一个F记录子树内的一个G记录子树外的还有一种就是有环的做过要用状压搞一下

不说这么多直接上例题

[HAOI2015]T1

经典的树形dp 这个转移有点难想比较不常规通常树形dp都是几乎是O(1)转移的这个转移是N的所有总的时间复杂度是N^2的等等讲细一点

首先我们可以染k个点第一个想的就是F[i][k]表示第i个点为子树可以染k个点然后的话就从下往上维护这个好像有点经典维护的方法第一次接触有点难

它的维护方法就像一个一次装箱但是的话好像这个装箱有点复杂因为有很多个点然后的话我是这么搞得

首先我们单单是维护子树下的话是有点难搞的因为有些黑点你要找到它的lca然后才把路径扫这样的话我们直接维护这个子树的黑点和白点已经确定了的费用

也就是黑白点在外面的一定要过我到孩子的边我就统计一下外面的白色点*里面的白色点*这条边的权值这个就是这个状态这条边做出的贡献黑点一样做

然后我们维护一个点的子树一个个子树和根节点合并假设我根结点现在已经有i个黑点下面有j个黑点那么就转移到F[i+j] 当然这样的时候会重复叠加也就是

当i=0 j=1时算了一个F[i+j]的状态到i=1 j=0的时候就会加上我当前F[i+j]的状态然后的话就会错了所以我们要一个数组保存以上上一个状态避免这种情况这个细节很重要

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#define Maxn 2010
using namespace std;
typedef long long LL;
struct node
{
  LL x,y,d,next;
}edge[Maxn*2]; LL len,first[Maxn];
void ins(LL x,LL y,LL d){len++; edge[len].x=x; edge[len].y=y; edge[len].d=d; edge[len].next=first[x]; first[x]=len;}
LL N,K; LL size[Maxn]; LL w[Maxn]; LL F[Maxn][Maxn]; LL G[Maxn];
void Dfs(LL x,LL fa)
{
  size[x]=1;
  for(LL k=first[x];k!=-1;k=edge[k].next)
  {
    LL y=edge[k].y;
    if(y!=fa)
    {
      w[y]=edge[k].d; Dfs(y,x);
      for(LL i=0;i<=min(size[x],K);i++) G[i]=F[x][i];
      
      for(LL i=0;i<=min(size[x],K);i++)
        for(LL j=0;j<=min(size[y],K);j++)
          if(i+j<=K)
            F[x][i+j]=max(F[x][i+j],G[i]+F[y][j]);
      size[x]+=size[y];
    }
  }
  if(x!=1)
    for(LL i=0;i<=min(size[x],K);i++)
      F[x][i]=F[x][i]+(i*(K-i)*w[x])+((size[x]-i)*(N-K+i-size[x])*w[x]);
}
int main()
{
  scanf("%lld%lld",&N,&K); len=0; memset(first,-1,sizeof(first));
  for(LL i=1;i<N;i++){LL x,y,d; scanf("%lld%lld%lld",&x,&y,&d); ins(x,y,d); ins(y,x,d);}
  memset(F,0,sizeof(F));
  Dfs(1,0); return printf("%lld
",F[1][K]),0;
}
/*
3 1
1 2 1
1 3 2
*/

View Code