树形dp基础

发表于 | 分类于 |

即状态转移关系以树形结构为基础的dp

例题1：https://www.luogu.com.cn/problem/UVA1292

以最少的点覆盖整颗树，则dp[i][1]表示覆盖以i为根的树，选择了i节点的最少节点数，dp[i][0]则表示没选择i节点的最少节点数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void dfs(int u,int fa)
{
    dp[u][1]=1;
    dp[u][0]=0;
    for(int i=0;i<g[u].size();i++)
    {
        if(g[u][i]!=fa)
        {
            int v=g[u][i];
            dfs(g[u][i]);
            dp[u][0]+=dp[v][1];//不选u则v必选
            dp[u][1]+=min(dp[v][1],dp[v][0]);//选u时v可选可不选
		}
	}
}

例题2：https://www.luogu.com.cn/problem/P2014

可将每棵子树看作一个容量为N的背包问题，即树形背包

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void dfs(int u)
{
    dp[u][0]=0;
    dp[u][1]=val[u];
    for(int i=0;i<g[u].size();i++)
    {
        dfs(g[u][i]);
        int v=g[u][i];
        for(int j=N+1;j>1;j--)//分配给u的总节点数,注意需要从大到小更新
        {
            for(int k=0;k<j;k++)//枚举分配给v的
            {
                dp[u][j]=max(dp[u][j],dp[v][k]+dp[u][j-k]);
            }
        }
    }
}

注意通过设0节点将森林变成树，0必选，故背包容量为N+1

时间复杂度为

易知在枚举背包容量时，有许多容量是不需要枚举的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void dfs(int u)
{
    sz[u]=1;
    dp[u][0]=0;
    dp[u][1]=val[u];
    for(int i=0;i<g[u].size();i++)
    {
        int v=g[u][i];
        dfs(v);
        for(ll j=min(N+1,sz[u]+sz[v]);j>1;j--)
        {
            for(ll k=max(0,j-sz[u]);k<=min(j,sz[v]);k++)
            {
                dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]);
            }
        }
        sz[u]+=sz[v];
    }
}

优化后时间复杂度转为

大致计算如下：考虑以u为根节点的子树，其子节点为v1、v2….

则合并时t=size[v1]*size[v1]+(size[v1]+size[v2])*size[v2]+…

t=size[u]*size[u]

其子节点合并复杂度为size[v]*size[v]，远小于t，递归下去，复杂度为

感觉还是不太理解orz

参考：

https://ouuan.github.io/post/%E6%A0%91%E4%B8%8A%E8%83%8C%E5%8C%85%E7%9A%84%E4%B8%8A%E4%B8%8B%E7%95%8C%E4%BC%98%E5%8C%96/