树形DP

是在树上进行的动态规划，所以一般采用递归的方式计算状态的转移

https://www.luogu.com.cn/problem/P1352

一道经典的树形DP问题引入

int n;
vector<int> e[6010];
int a[6010];
bool st[6010];
int dp[6010][2];

void dfs(int x){
    dp[1]=a;
    for (auto v:e){
        dfs(v);
        dp[1]+=dp[v][0];
        dp[0]+=max(dp[v][1],dp[v][0]);
    }
}

void solve(){
    cin>>n;
    for (int i=1;i<=n;i++) cin>>a[i];
    for (int i=1;i<n;i++){
        int l,k;
        cin>>l>>k;
        e[k].push_back(l);
        st[l]=1;
    }
    for (int i=1;i<=n;i++){
        if (st[i]==0){
            dfs(i);
            cout<<max(dp[i][0],dp[i][1]);
            break;
        }
    }
}

我们定义 $dp_{i,0}$ 表示不选 $i$ 节点的的最大指数，$dp_{i,1}$ 表示选择 $i$ 节点的最大指数

根据题目可以得出规则：如果选一个节点，那么他的子节点不能选；如果不选一个节点，那么他的子节点可选可不选

所以写出状态转移方程：其中 $j$ 表示 $i$ 的子节点

$$ dp_{i,1}=\sum_j dp_{j,0}\\ dp_{i,0}=\sum_j {\rm{max}}(dp_{j,0},dp_{j,1}) $$

对于 $i$ 节点不选择的状态，从他的子节点的两个状态中选取最佳的状态进行转移

在 DFS 过程中，$dp$ 状态通常为当前节点的最优解，上面的题目中，我们在后序遍历回溯时，总是上传子节点的最优解给父节点进行状态转移，最终到达根节点为全局最优解

与边有关的树形DP

https://www.luogu.com.cn/problem/P2015

struct edge{
    int v,w;
};

int n,q;
vector<edge> e[110];
int dp[110][110];
int a[110];

void dfs(int x,int p){
    dp[0]=a;
    for (auto it:e){
        if (it.v==p) continue;
        a[it.v]=it.w;
        dfs(it.v,x);
        for (int i=q;i>=1;i--){
            for (int j=0;j<=i-1;j++){
                dp[i]=max(dp[i],dp[i-j-1]+dp[it.v][j]);
            }
        }
    }
}

void solve(){
    cin>>n>>q;
    for (int i=1;i<n;i++){
        int u,v,w;
        cin>>u>>v>>w;
        e[u].push_back({v,w});
        e[v].push_back({u,w});    
    }
    dfs(1,-1);
    cout<<dp[1][q];
}

给出的边连接树上两个点，边权为这个边上的苹果数量，可以看做这个边连接的儿子拥有的苹果数量

所以在 DFS 过程中应该记录当前儿子节点的苹果数

a[it.v]=it.w;

定义 $dp_{i,j}$ 表示节点 $i$ 有 $j$ 个树枝的最大苹果数，初始化时 $dp_{i,0}=a_i$ 即每个节点如果只选自己，那么苹果数就为这个树枝上的苹果数

考虑状态的转移，其中 $x,v$ 分别表示父节点和他的一个子节点

$$ dp_{x,i}={\rm{max}}(dp_{x,i},dp_{x,i-j-1}+dp_{v,j}) $$

形象化的说，父节点有 $i$ 个树枝的最大苹果数由他的子节点 $v$ 有 $j$ 个树枝的状态转移

因为连接子树需要额外的一条边，所以如果选取一个有 $j$ 条边的子节点的状态，那么父节点的边数需要多减一即 $i-j-1$

树上背包问题

https://www.luogu.com.cn/problem/P2014

int n,m;
int a[310];
vector<int> e[310];
int dp[310][310];

void dfs(int x){
    for (int i=1;i<=m;i++) dp[i]=a;
    for (auto v:e){
        dfs(v);
        for (int i=m;i>=1;i--){
            for (int j=0;j<=i-(x!=0);j++){
                dp[i]=max(dp[i],dp[i-j]+dp[v][j]);
            }
        }
    }
}

void solve(){
    cin>>n>>m;
    for (int i=1;i<=n;i++){
        int k;
        cin>>k;
        e[k].push_back(i);
        cin>>a[i];
    }
    dfs(0);
    cout<<dp[0][m];
}

定义 $dp_{i,j}$ 表示第 $i$ 个节点容量为 $j$ 时能得到的最大学分，因为每门课所占体积都为 $1$ ，所以这里的 $j$ 也可以表示选 $j$ 门课

对于每个节点，都可以看作是一个容量为 $j$ ，在他子节点中选取物品的背包问题

形如

for (auto v:e){
    for (int i=m;i>=1;i--){
        
    }
}

第一层找子节点的循环可以类比 01背包的第一层循环，即在前 $u$ 个物品中选

第二层的枚举背包容量同理，注意这里的 $dp$ 状态利用滚动数组的方式优化掉了第二维

for (int j=0;j<=i-(x!=0);j++)//x!=0表明不是虚拟根节点，需要预留选父节点容量1

第三层循环的目的是在节点容量为 $i$ 下，枚举决策数，例如容量为 $x$ 的背包，我们可以在第一层枚举的前 $u$ 个子节点中选取很多个不同的组合

状态的转移可以被描述为：

对于 $i$ 节点容量为 $j$ 的状态，由他的子节点的从 $[1,j]$ 的容量组合进行转移

dp[i]=max(dp[i],dp[i-j]+dp[v][j]);

代码中父节点的容量被定义为 $i$ ，对于从 $[1,m]$ 的容量，我们对每个容量的状态都再多循环一层决策

即在容量为 $i$ 下，将 $i$ 拆分为哪两个组合最优：是原有状态还是将 $i$ 拆分为 $j,i-j$ 这两个容量

其中 $j$ 容量表示子节点组合出的总体积为 $j$ 的最优方案，$i-j$ 容量为其他子树的贡献

类似于 01背包的 dp[j]=max(dp[j],dp[j-w[i]]+v[i])