树上DP

前置知识：图与树入门、动态规划

树的子树结构有天然有子结构性质，一般是依次来进行动态规划

令 dp[now] 表示 now 节点的子树的信息，然后将一个节点的多个儿子的信息合并

例：

有 $n$ 个人，除了大老板外每个人有一个直系上司，所有人形成一颗树。

现在举办一个舞会，如果一个人的直系上司来了，那么它就不回来，请问最多会来几个人？

令 dp[now][0/1] 表示 now 本人来或不来时，now 的子树内最多来几个人

由儿子的子树转移过来，假设 t 是 now 的儿子

如果 now 来，那么只能 t 不来：dp[now][1]+=dp[t][0]

如果 now 不来，那么 t 来或不来都可以：dp[now][0]+=max(dp[t][0],dp[t][1])

最后记得算上 now 自己的贡献

cpp

void dfs(int now,int fa)
{
	for(int t:eg[now])
	{
		if(t==fa) continue;
        dfs(t,now);
        dp[now][1]+=dp[t][0];
        dp[now][0]+=max(dp[t][1],dp[t][0]);
	}
    dp[now][1]++;//算上自己
}

P1352 没有上司的舞会

P1122 最大子树和

树上背包

我们将背包问题放到树上（又称有依赖的背包）

假设有 $n$ 个物品，除了某个物品之外，选某个物品必须先选择另一个物品，所有依赖关系形成一棵树（没有环依赖）

选 $m$ 个物品最多获得多少价值？

仍然以子树为子结构，设 dp[now][k] 表示 now 的子树中选了 $k$ 个物品的最多价值

按照背包的方式进行转移

cpp

void dfs(int now,int fa)
{
    for(int t:eg[now])
    {
        if(t==fa) continue;
        dfs(t,now);
        for(int j=m;j>=1;--j)//一共选了几个物品，注意从大到小，原因在背包那一节讲过
        {
            for(int k=0;k<=j;++k)//子树选几个
            {
                dp[now][j]=max(dp[now][j],dp[now][j-k]+dp[t][k]);
            }
		}
	}
    for(int j=m;j>=1;--j)
    {
        dp[now][j]=dp[now][j-1]+val[now];//选子树必须要选自己
    }
}

观察循环和递归可以得出这个是 $O (n m^{2})$ 的算法

有一些部分是多余的，没有必要处理，比如我们枚举了上界是 $m$ ，但是可能子树里没有 $m$ 个节点

cpp

void dfs(int now,int fa)
{
    str[now]=0;
    for(int t:eg[now])
    {
        if(t==fa) continue;
        dfs(t,now);
        for(int j=0;j<=str[now];) tmp[j]=dp[now][j];
        for(int j=0;j<=str[now];++j)//之前选几个物品
        {
            for(int k=0;k<=str[t]&&j+k<=m;++k)//子树选几个物品
            {
                dp[now][j+k]=min(dp[now][j+k],tmp[now][j]+dp[t][k]);
            }
		}
        str[now]+=str[t];
	}
    ++str[now];
    for(int j=m;j>=1;--j)
    {
        dp[now][j]=dp[now][j-1]+val[now];//选子树必须要选自己
    }
}

这样相当于卡死了上下界

这个循环：

cpp

for(int j=0;j<=str[now];++j)
{
    for(int k=0;k<=str[t]&&j+k<=m;++k)
    {
        
    }
}

str[now] 是之前子树的节点个数，str[t] 是 t 子树的节点个数，这两个嵌套起来相当于是在 now 的所有子树里面，任意选两个节点的方案数。

反过来说，任意两个节点也只会在最近公共祖先（LCA）处被合并一次，所以这部分合并的总复杂度是 $O (n^{2})$ 的。

总复杂度是指所有节点作为 now 时，这两个循环带来的复杂度求和是 $O (n^{2})$ 级别的。

还有更严格的上界：

参考

定义子树节点个数超过 $m$ 的子树为大子树，不超过 $m$ 的子树为小子树

极小大子树：没有任何一个儿子是大子树的大子树

极大小子树：父亲是大子树的小子树

假设小子树的大小为 $x_{1}, x_{2}, \dots, x_{k} < m$

小子树内部互相合并的复杂度 $x_{1}^{2} + x_{2}^{2} + \dots + x_{k}^{2}$

最坏情况下是每一个 $x_{i}$ 都等于 $m$ ，复杂度是 $\frac{n}{m} * m^{2} = n m$

极小大子树全都合并起来的复杂度：极小大子树不会超过 $\frac{n}{m}$ 个，合并两个的花费是 $m^{2}$ ，所以花费是 $O (n m)$

大子树和小子树合并的复杂度： $m * (x_{1} + x_{2} + \dots + x_{k}) \leq n m$

所以总时间复杂度是 $O (n m)$

P2014 [CTSC1997] 选课

P2015 二叉苹果树

P1040 [NOIP2003 提高组] 加分二叉树树上dp和区间dp的结合

P1273 有线电视网

换根DP

先看一个简单的题：

求以 $1$ 根节点时，所有节点的深度之和。

只要求出所有节点的深度，加起来就可以了。

加强一下这个题：求一个节点，以该节点为根时，所有节点的深度之和最大。

考虑另一个问题：

本来根节点在 $1$ 号点，我们知道以 $1$ 为根节点时，所有点的深度之和 $s u m$ 。

现在要把根移动到和 $1$ 相邻的 $2$ 号点，移动之后所有节点的深度之和是多少？

假设有 $n$ 个节点， $s t r [x]$ 是 $x$ 节点的子树的方案数。

那么 $2$ 号点所有的子树的深度都减少 $1$ ，那么 $s u m - = s t r [2]$ 。

$2$ 号点上方的点的深度都增加 $1$ ，那么 $s u m + = (n - s t r [2])$ 。

通过 $O (1)$ 得到了 $2$ 号点的答案。

也就是说，可以通过一定的信息， $O (1)$ 的得到根节点从一个点移动到另一个相邻的点的答案。

那么可以先通过一遍遍历，求出以 $1$ 为根的答案，再通过第二遍遍历，求出其他节点为根的答案。

cpp

void dfs1(int now,int fa)
{
    str[now]=1;
    dep[now]=dep[fa]+1;
    sum+=dep[now];
    for(int t:eg[now])
    {
        if(t==fa) continue;
        dfs1(t,now);
        str[now]+=str[t];
    }
}
void dfs2(int now,int fa)
{
    ans=max(ans,sum);
    for(int t:eg[now])
    {
        if(t==fa) continue;
        sum-=str[t];
        sum+=n-str[t];
        str[now]-=str[t];//更改一下 now 和 t 的子节点。
       	str[t]+=str[now];
        dfs2(t,now);
        str[t]-=str[now];
        str[now]+=str[t];
        sum+=str[t];
        sum-=n-str[t];
    }
}

P3478 [POI2008] STA-Station

P2986 [USACO10MAR] Great Cow Gathering G

P6419 [COCI2014-2015#1] Kamp

树上DP ​

树上背包 ​

换根DP ​

树上DP

树上背包

换根DP