【6】树形DP学习笔记

w9095 · 2024-04-13 13:58:53 · 算法·理论

前言

教练说过，树形 DP 是一个抽象的东西，很多状态比较难以理解，后面具体的学习方法，忘了。

UPD on 2024.11.21：修复了例题 5 的假做法和假代码。

普通树形 DP

树形 DP 是一类在树上的动态规划，通常以节点位置作为阶段，树中的父子关系为转移，边界状态是叶子节点，目标是根节点。记 son(x) 为 x 的子节点的集合，op(x,y) 为 x\to y 转移的贡献，则树形 DP 的状态转移方程类似这两种形式：

由于跨层转移难以处理，所以我们一般设计可以父子转移的状态。

例题 1：

P1352 没有上司的舞会

令 1 为根节点。设状态 f_{x,0} 表示点 x 不去的情况，f_{x,1} 表示点 x 去的情况。

如果点 x 不去，则它的儿子节点可以去或者不去，在 f_{y,0} 和 f_{y,1} 中取较小值。因此，有以下转移方程：

如果点 x 去，则它的儿子节点不可以去，取 f_{y,0}。因此，有以下转移方程：

边界情况是叶节点 x，f_{x,0}=0,f_{x,1}=a_x，目标是是根节点，可以去或不去，取 f_{1,0} 和 f_{1,1} 的较小值。

#include <bits/stdc++.h>
using namespace std;
struct edge
{
    int v,nxt;
}e[400000];
int n,m,u,v,a[400000],h[400000],f[400000][2],cnt=0;
void add_edge(long long u,long long v)
{
    e[++cnt].nxt=h[u];
    e[cnt].v=v;
    h[u]=cnt;
}

void dfs(long long x,long long fa)
{
    f[x][1]=a[x];
    for(int i=h[x];i;i=e[i].nxt)
        if(e[i].v!=fa)
           {
           dfs(e[i].v,x);
           f[x][0]+=max(f[e[i].v][0],f[e[i].v][1]);
           f[x][1]+=f[e[i].v][0];
           }
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=n-1;i++)
        {
            scanf("%d%d",&u,&v);
            add_edge(u,v),add_edge(v,u);
        }
    dfs(1,0);
    printf("%lld",max(f[1][0],f[1][1]));
    return 0;
}

例题 2：

CF1929D Sasha and a Walk in the City

我们把选取到的点称为黑点，由题意得，一个合法的点集能使树中任意一条简单路径上的黑点数量不超过两个。也就是说，如果黑点数量多于 2，对于任意两个黑点，它们如果在同一个节点的子树内，必然是兄弟关系。否则，一旦存在祖先关系，由于黑点数量多于 2，必然有一个黑点可以与这两个点组成一条黑点数量超过两个的简单路径。

设状态 f_{i,j} 表示以 i 为根的子树内，从根到叶子节点最多经过 j 个黑点。显然，只有 j 等于 0,1 或 2 时，状态是合法的。

考虑如何转移，对于 f_{i,0}，显然等于 1。

对于 f_{i,1}，由于根到叶子节点最多经过黑点数最大值为 1，最多就是两条到根的路径合并，经过 1+1=2 个黑点，所以每一个儿子内可以任意选择。另外，每个子树内还可以从没有黑点涂子树的根上的黑点变成有 1 个黑点，所以还需要加入没有黑点的方法数。根据乘法原理，可以推出如下转移式：

对于 f_{i,2}，由于根到叶子节点最多经过黑点数最大值为 2，所以只能有一个子树内的 f 值可以转移来，否则必然可以构造一条黑点数量超过两个的简单路径。另外，每个子树内还可以从 1 个黑点涂子树的根上的黑点变成有 2 个黑点，所以还需要加入 1 个黑点的方法数。根据加法原理，可以推出如下转移式：

以 1 为整棵树的根，最后的答案为 f_{1,0}+f_{1,1}+f_{1,2}，也就是 1+f_{1,1}+f_{1,2}。

#include <bits/stdc++.h>
using namespace std;
struct edge
{
    long long v,nxt;
}e[800000];
long long t,u,v,n,mod=998244353,h[800000],f[800000][3],cnt=0;
void add_edge(long long u,long long v)
{
    e[++cnt].nxt=h[u];
    e[cnt].v=v;
    h[u]=cnt;
}

void init()
{
    for(int i=1;i<=n;i++)h[i]=0,f[i][1]=1,f[i][2]=0;
    cnt=0;
}

void dfs(long long x,long long fa)
{
    for(int i=h[x];i;i=e[i].nxt)
        if(e[i].v!=fa)
           {
           dfs(e[i].v,x);
           f[x][1]=(f[x][1]*(f[e[i].v][1]+1)%mod)%mod; 
           f[x][2]=(f[x][2]+f[e[i].v][1]+f[e[i].v][2])%mod;
           }
}

int main()
{
    scanf("%lld",&t);
    while(t--)
       {
        scanf("%lld",&n);
        init();
        for(int i=1;i<=n-1;i++)
            {
            scanf("%lld%lld",&u,&v);
            add_edge(u,v),add_edge(v,u);
            }
        dfs(1,0);
        printf("%lld\n",(f[1][1]+f[1][2]+1)%mod);
       }
    return 0;
}

例题 3：

P2279 [HNOI2003] 消防局的设立

主要参考 这篇题解。

对于每个点 x，有五个状态：