树形dp

树形dp，即在树上进行的 dp。由于树固有的递归性质，树形 DP 一般都是用dfs来递归进行的。

主要的思路就是计算子树，然后合并

模版大概是这样的

void dfs(int u, int fa){
  	for(int i = head[u]; i; i = tr[i].to){
    		int v = tr[i].to;
    		if(v == fa)continue;
    		dfs(v, u);
      
      //接下来再进行dp的更新
      
      
  	}
}

题型一般分为两种：选择节点类、树形背包类

选择节点类

dp[u][0] = dp[v][1];
dp[u][1] += max/min(dp[v][0], dp[v][1]);

选择节点式的题，首先前提条件是整个数据是由树形结构存储的，或者应该用树形结构存，然后会告诉你上下相邻的节点是不能同时存在的，要求取最大最小值 ，类似 没有上司的舞会、Strategic game 等

没有上司的舞会

题目描述：

一颗树，一个点不能和他的父亲节点一起参会，每个点都有一个价值，问最大价值是多少

思路：

dp[i][0]表示以 i 为根节点时不选节点 i 时的子树能获得的最大价值

dp[i][1]表示以 i 为根节点时选节点 i 时的子树能获得的最大价值

显然dp[i][0]可以由dp[v][0] 和 dp[v][1]转移而来

dp[i][1]只能由dp[v][0]转移而来

所以

dp[u][0] += max(dp[v][0], dp[v][1]);
dp[u][1] += dp[v][0];

赋初始值：dp[u][1] = val[u]

剩下的就套刚才的模版就行

这个题是个无根树，也就是没规定谁是根，那就随便取1当根

int tot;
int head[MAX];
struct ran{
    int to, nex;
}tr[MAX];
inline void add(int u, int v){
    tr[++tot].to = v;
    tr[tot].nex = head[u];
    head[u] = tot;
}

int dp[6005][2];
int val[6005];
int ans;

void dfs(int u, int pre){
    dp[u][1] = val[u];
    for(int i = head[u]; i; i = tr[i].nex){
        int v = tr[i].to;
        if(v == pre)continue;
        dfs(v, u);
        dp[u][0] += max(dp[v][0], dp[v][1]);
        dp[u][1] += dp[v][0];
    }
}

void work(){
    cin>>n;
    for(int i = 1; i <= n; ++i)cin>>val[i];
    for(int i = 1; i < n; ++i){
        cin>>x>>y;
        add(x, y);
        add(y, x);
    }
    cin>>x>>y;
    dfs(1, 0);
    cout<<max(dp[1][0], dp[1][1])<<endl;
}

Strategic game

题目描述：

n个点，n-1条边，一棵树，一个如果被覆盖，则与他相连的点也都被覆盖，问最少选择多少个点可以覆盖所有的点

思路：

dp[i][0]表示不选 i 点时以 i 为根节点覆盖子树所有点的最小选择数量

dp[i][1]表示选 i 点时以 i 为根节点覆盖子树所有点的最小选择数量

很显然dp[i][0]可以由dp[v][1]与dp[v][0]转移而来

dp[i][1]可以由dp[v][1]转移而来

所以

dp[u][0] += dp[v][1];
dp[u][1] += min(dp[v][0], dp[v][1]);

其他的和上面那个题一样了就，没什么好说的

树上背包

简单的来说就是树形dp与分组背包问题的结合

选课

题目描述：

每门课都有各自的学分，有些课需要在别的课学完以后才可以学，你可以修M门课，问能获得的最大学分是多少

思路：

dp[i][j][k]表示以 i 为根节点时，前 j 个节点，选 k 门课能获得的最大的学分

显然dp[i][1][1] = val[i]

状态转移方程：

dp[i][j][k] = max(dp[i][j - 1][k], dp[v][所有节点数][l] + dp[i][j - 1][k - l])

这其实就是一个背包问题了，可以滚掉中间那一维，只需要向背包那样倒着枚举可选课程数量就行

我们可以把他理解成一个分组背包，分组背包就是先枚举每个组，再枚举体积，再枚举每个组的每个物品

这里可以理解成先枚举每个子树的顶点v，再枚举可选课程的数量，也就是背包的体积，再枚举每个物品，虽然都是以v为根节点的子树，看样子是一个物品，但是他们的占的体积是不一样的，所以第三层的循环可以看出是枚举该物品所有的可能的体积

for(int i = head[u]; i != -1; i = tr[i].nex){//枚举子树
  int v = tr[i].to;
  dfs(v);
  for(int j = m + 1; j >= 1; --j){//枚举体积
      for(int k = 0; k <= j - 1; ++k){//枚举子树的体积
          dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[v][k]);
      }
  }
		}
}

 

int tot;
int head[MAX];
struct ran{
    int to, nex;
}tr[MAX];
inline void add(int u, int v){
    tr[++tot].to = v;
    tr[tot].nex = head[u];
    head[u] = tot;
}

int val[MAX];
int dp[305][305];

void dfs(int u){
    for(int i = head[u]; i != -1; i = tr[i].nex){ 
        int v = tr[i].to;
        dfs(v);
        for(int j = m + 1; j >= 1; --j){ 
            for(int k = 0; k <= j - 1; ++k){
                dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[v][k]);
            }
        }
    }
}

void work(){
    mem(head, -1);
    cin>>n>>m;
    for(int i = 1; i <= n; ++i){
        cin>>x>>dp[i][1];
        add(x, i);
    }
    dfs(0);
    cout<<dp[0][m + 1]<<endl;
}

int main(){
//    io;
//    int tt;cin>>tt;
//    for(int _t = 1; _t <= tt; ++_t){
//        printf("Case #%d: ", _t);
        work();
//    }
    return 0;
}