bzoj 4711 小奇挖矿 ——“承诺”类树形dp

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=4711

对“承诺”有了更深的了解。

向外和向内要区分，所以 f [ i ][ j ] 表示根向外 j 步有仓库；g[ i ][ j ]表示根向内 j 步有仓库。

转移的时候要注意，要保证承诺的那个地方确实有仓库；通过 cr 之前的孩子 或 当前孩子 的那个地方的承诺来保证；剩下的部分不用保证那儿有仓库，用自己的最小值转移即可；

一棵子树如果承诺自己内部某个地方有仓库，就一定已经有了；但承诺外部的某个地方有仓库却只是承诺；所以可以对 g[ ][ ] 取min来做那个随便的转移，却不能随便对待 f [ ][ ]。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int N=,INF=1e9;

int n,d[N],K,hd[N],xnt,to[N<<],nxt[N<<];

int f[N][N],g[N][N],mn[N];

void add(int x,int y)

{

  to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;

  to[++xnt]=x;nxt[xnt]=hd[y];hd[y]=xnt;

}

void dfs(int cr,int fa)

{

  for(int i=;i<n;i++)f[cr][i]=d[i],g[cr][i]=INF;

  f[cr][n]=g[cr][n]=INF;

  f[cr][]=g[cr][]=K; mn[cr]=K;//mn[cr]=K

  for(int i=hd[cr],v;i;i=nxt[i])

    if((v=to[i])!=fa)

      {

    dfs(v,cr);

    for(int j=;j<n;j++)

      {

        if(j)

          g[cr][j]=min(g[cr][j]+min(f[v][j+],mn[v]),

               g[v][j-]+min(mn[cr],f[cr][j]));

        else g[cr][j]+=min(f[v][j+],mn[v]);

        f[cr][j]=min(f[cr][j]+min(mn[v],f[v][j+]),f[v][j+]+mn[cr]);

        //printf("f[%d][%d]=%d g[%d][%d]=%d\n",cr,j,f[cr][j],cr,j,g[cr][j]);

      }

    mn[cr]=g[cr][];

    for(int j=;j<n;j++)min(mn[cr],g[cr][j]);

      }

  mn[cr]=g[cr][];

  for(int i=;i<n;i++)mn[cr]=min(mn[cr],g[cr][i]);

}

int main()

{

  scanf("%d%d",&n,&K);

  for(int i=;i<n;i++)scanf("%d",&d[i]);

  for(int i=,u,v;i<n;i++)

    {

      scanf("%d%d",&u,&v);add(u,v);

    }

  dfs(,);

  printf("%d\n",min(mn[],f[][]));

  return ;

}