树形dp在算法竞赛中的应用

[[ slider_text ]]

[[ item.c ]]

树形dp在算法竞赛中的应用

发布时间 2024-05-26 作者：秋千月 来源：代码源，OI-WIKI, codeforces

树形dp dp计数

## 2021 Nanjing H. Crystalfly
**问题描述**
**[H. Crystalfly](https://codeforces.com/gym/103470/problem/H)**
给定一个$$n$$个点的树，第$$i$$个点有$$a_i$$只蝴蝶
每次到达一个顶点，可以抓住这个顶点上所有的蝴蝶，但是一旦到了这个点，所有和它相临的蝴蝶都会被惊动
第$$i$$个点的蝴蝶，在$$t$$时刻被惊动了，会在$$t+t_i$$时刻消失，其中$$1 \leqslant t_i \leqslant 3$$
在$$0$$时刻在$$1$$号点，接下来每时每刻可以移动到一个相临点，并且停留到下个时刻开始
问最后能抓住多少只蝴蝶

每个时刻你可以挪一次，或者不动

### 算法分析
考虑两个问题
第一，路径不可能折返
第二，要么碰一个点后立马返回，然后找一个$$t_i = 3$$的**兄弟**，深入下去
![](/media/content_img/treedp-01.png)
![](/media/content_img/treedp-02.png)

### 算法设计

> 如何设计 dp 的状态，考虑一个点有没有蝴蝶，以及怎么走

![](/media/content_img/treedp-03-1.png)
![](/media/content_img/treedp-03-2.png)

> dp3 和 dp1 的转移已经有了，现在考虑 dp1 中$$u, v$$之间的转移

![](/media/content_img/treedp-04.png)
![](/media/content_img/treedp-05.png)

> 直接 dp 的话需要 for$$v_i, v_j$$，肯定是$$O(n^2)$$的，考虑优化

注意到这里关于$$v_j$$的量$$a(v_j)$$是已知的，可以通过预处理完成
![](/media/content_img/treedp-06.png)
![](/media/content_img/treedp-07.png)

### 算法实现
**找最大值和次大值**
```bash
定义二元组 (val, idx)

pair<long long, int> ma1(-inf, 0), ma2(-inf, 0);
for (auto v : G[u]) if (v != pa) {
	pair<long long, int> ma3(a[v], v);
	if (ma2 < ma3) ma2 = ma3;
	if (ma1 < ma2) swap(ma1, ma2);
}
```

**注意**，**有条件的转移**表达式，比如$$\max ([t_v = 3] \cdot a_v)$$
可以在`dp`的时候，令**最大值和次大值**`ma1, ma2`都设置为$$-\infty$$
只在$$t_v = 3$$的时候，更新**最大值和次大值**，然后统一都用`ma1, ma2`去转移
这样，如果不合法的情况，值就是$$val = -\infty$$，在`chmax( dp1[u],  val )`转移时候不影响
这样可以省去很多麻烦的边界讨论

## 2020 Nanjing M.Monster Hunter
**问题描述**
**[Monster Hunter](https://ac.nowcoder.com/acm/contest/10272/M)**
给定一个$$n$$个点的有根树，一开始在第$$i$$个点有血量为$$hp_i$$的怪物
你想要消灭所有怪物，一个怪物被消灭，当且仅当它的父亲被消灭，它才能被消灭
消灭的力量为这个怪物和它未被消灭的儿子的 hp 总和

你可以使用$$m$$次魔法，使用一次你可以没有额外限制用$$0$$的力量消灭一个点的怪物
你希望使用魔法，使得消灭剩下点的力量之和最小
输出$$m = 0, 1, 2, ..., n$$的答案

### 算法分析
> 考虑树上背包，点对答案的贡献

![](/media/content_img/treedp-08-1.png)

### 算法设计
![](/media/content_img/treedp-08-2.png)

## 2020 Qinghuangdao K.Kingdom's Power
**问题描述**
**[kingdom's power](https://codeforces.com/gym/102769/problem/K)**
给定一个$$n$$个点的有根树，一开始在第一个点上有无数军队
每一秒，可以指挥任意一支军队到一个相邻点，希望每个点都有一个军队访问过，问最少需要多少时间

### 算法分析

> 这种问题，**拐点**很重要

![](/media/content_img/treedp-09-1.png)

### 算法设计
这个问题设计算法，以及 dp 的状态，同样可以根据**拐点**来设计
![](/media/content_img/treedp-09-2.png)
![](/media/content_img/treedp-09-3.png)

如图所示，一种情况是，$$u$$不是拐点，拐点在祖先处
第二种情况是，从根节点指派新的军队，$$u$$作为拐点

需要注意的是，第二种情况**一定要保证$$u$$是作为拐点的**
这又对应两种决策，第一就是$$u$$原先不是拐点，那么新合并的分支$$v$$，要使得$$u$$成为新的拐点
第二种就是$$u$$原先就是拐点了，那么$$v$$既可以直接用$$u$$的军队，也可以从根节点指派（让$$u$$再次成为拐点）

## CF 734(Div 3) F. Equidistant Vertices
**问题描述**
**[F.Equidistant Vertices](https://codeforces.com/contest/1551)**
给定一个$$n$$个点的树，选择一个大小为$$k$$的子集，使得这些点两两之间距离相同
问方案数是多少

### 算法分析
考虑树上距离两两相等的点，一定有分叉的形状
![](/media/content_img/treedp-10-1.png)
据此，可以考虑枚举分岔点，枚举深度来求解

### 算法设计
![](/media/content_img/treedp-10-2.png)

问题转换成为不同集合中，选出位于**不同集合**的$$k$$个点，类似一个**背包计数**
实现的时候注意，第二维要倒着 for，`for j = k down to 1`

### 算法实现
```bash
void solve() {
    int n, K;
    scanf("%d%d", &n, &K);

vector<vector<int> > G(n+1, vector<int>());
    for (int i = 0; i < n-1; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back(v), G[v].push_back(u);
    }

if (K == 2) {
        ll ans = 1LL * n * (n-1) / 2;
        ans %= P;
        printf("%lld\n", ans);
        return;
    }

function<void(int, int, int, int&)> dfs = [&](int u, int fa, int dep, int &cnt) -> void {
        if (dep == 0) {
            cnt += 1;
            return;
        }
        for (auto v : G[u]) if (v != fa) {
            dfs(v, u, dep-1, cnt);
        }
    };

mint ans = mint(0);
    for (int d = 1; d <= n; d++) {
        for (int u = 1; u <= n; u++) {
            vector<mint> dp(K+1, mint(0));
            dp[0] = mint(1);

for (auto v : G[u]) {
                int cnt = 0;
                dfs(v, u, d-1, cnt);

for (int j = K; j >= 1; j--) {
                    dp[j] = dp[j] + dp[j-1] * mint(cnt);
                }
            }

ans = ans + dp[K];
        }
    }

printf("%d\n", ans.val());
}
```

上一篇：树上动态规划（路径问题）下一篇：数位dp（一）

看完文章有啥想法

算法小站

树形dp在算法竞赛中的应用