本期笔记的内容为树形DP

相关链接：

1.往期笔记： 查看
2.来源：yxc老师的算法提高课

【提高版】DP知识笔记6 $\quad$ 有猷 编

树形DP是在树上进行的，通常用递归方式遍历所有状态。

下面的图就是一棵树

例题：

1. 树的中心

思路：
比较 烦 ，在这里给一下C++代码：

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
#define re register
#define Re register
#define MAXN 10005
struct node{
    int to,val;
};
int n,ans = 1e9,cnt[MAXN],lst[MAXN],F[MAXN];
vector<node>a[MAXN];
void dfs(int pos,int l,int fa){
    lst[pos] = l;
    F[pos] = fa;
    int ans = 0;
    for(re int i = 0;i < a[pos].size();i++){
        if(a[pos][i].to != fa){
            dfs(a[pos][i].to,l + a[pos][i].val,pos);
            cnt[a[pos][i].to] += a[pos][i].val;
            ans = max(ans,cnt[a[pos][i].to]);
        }
    }
    cnt[pos] = ans;
}
void dfs2(int i,int fa,int tmp){
    F[i] = fa;
    lst[i] = max(lst[i],lst[fa] + tmp);
    for(re int j = 0;j < a[F[i]].size();j++){
        if(a[F[i]][j].to != F[F[i]] && a[F[i]][j].to != i){
            lst[i] = max(lst[i],cnt[a[F[i]][j].to] + tmp);
        }
    }
    for(re int j = 0;j < a[i].size();j++){
        if(a[i][j].to != fa){
            dfs2(a[i][j].to,i,a[i][j].val);
        }
    }
}
int main() {
    scanf("%d",&n);
    for(re int i = 1;i < n;i++){
        int ai,bi,ci;
        scanf("%d%d%d",&ai,&bi,&ci);
        a[ai].push_back((node){bi,ci});
        a[bi].push_back((node){ai,ci});
    }
    dfs(1,0,0);
    dfs2(1,0,0);
    for(re int i = 1;i <= n;i++){
        int cont = lst[i];
        for(Re int j = 0;j < a[i].size();j++){
            if(a[i][j].to == F[i])continue;
            cont = max(cont,cnt[a[i][j].to]);
        }
        ans = min(ans,cont);
    }
    printf("%d\n",ans);
    return 0;
}

2. 二叉苹果树

思路：

3. 战略游戏（最大独立集问题）

思路：

4. 皇宫看守

思路：
有点 难 给下代码：

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
#define re register
#define Re register
#define MAXN 1505
int n,cost[MAXN],opt[MAXN][3];
bool fa[MAXN];
vector<int>a[MAXN];
void dfs(int pos){
    bool f = false;
    for(Re int i = 0;i < a[pos].size();i++){
        int tmp = a[pos][i];
        dfs(tmp);
        opt[pos][0] += min(opt[tmp][1],opt[tmp][2]);
        opt[pos][1] += min(opt[tmp][1],opt[tmp][2]);
        opt[pos][2] += min(min(opt[tmp][1],opt[tmp][2]),opt[tmp][0]);
        if(opt[tmp][2] <= opt[tmp][1])f = true;
    }
    opt[pos][2] += cost[pos];
    if(f)return;
    int t = 2e9;
    for(Re int i = 0;i < a[pos].size();i++){
        int tmp = a[pos][i];
        t = min(t,opt[tmp][2] - opt[tmp][1]);
    }
    opt[pos][1] += t;
}
int main() {
    scanf("%d",&n);
    for(re int i = 1;i <= n;i++){
        int c,k,m,u;
        scanf("%d%d%d",&c,&k,&m);
        cost[c] = k;
        while(m--){
            scanf("%d",&u);
            a[c].push_back(u);
            fa[u] = true;
        }
    }
    for(re int i = 1;i <= n;i++){
        if(!fa[i]){
            dfs(i);
            printf("%d\n",min(opt[i][1],opt[i][2]));
        }
    }
    return 0;
}