[树形DP] The 2021 ICPC Asia Nanjing Regional Contest H题

1.https://codeforces.com/gym/103470/problem/H

题意：

在一棵树上的每个节点都有不同数量的蝴蝶。当你进入一个节点时，若那个节点上有蝴蝶，你将会抓住那个节点的蝴蝶，但你会惊动那个节点的子节点里的蝴蝶。你从一个节点到另一个节点，并抓到蝴蝶的时间为1秒，被惊动的蝴蝶将会在$t_i(t_i<=3)$秒后飞走。

从顶点1开始，请问最多可以抓到多少蝴蝶？

题解：

将子树全部分成三种，一种是从子树根节点一直往下做，记为$f(x)$；一种是从子树的根节点已经被取走了，但是也从这个点出发一直往下做，记为$g(x)$；最后一种是进入一个根节点，但是立刻掉头回到原来的点，再走下一棵树，记为$h(x)$。

因此，我们可以得到一下公式$f(u)=a_u+g(u)，h(u)=a_u+\sum g(v)$。

接下来考虑$g_u$如何计算。

第一种情况，当我们从$u$节点到达一个子节点$v$之后就一直走下去，其他子节点的蝴蝶就无法抓到，那此时的状态转移方程为 g ( u ) = m a x { f ( v i ) + ∑ v j ≠ v i g ( v j ) } = m a x { a v } + ∑ g ( v ) g(u)=max{f(v_i) + sum_{v_jne v_i}{g(v_j)}}=max{a_v}+sum{g(v)} g(u)=max{f(vi​)+∑vj​​=vi​​g(vj​)}=max{av​}+∑g(v)，

第二种情况，但我们从$u$节点到达一个子节点$v$之后就掉头，去其他子树，这样子状态转移方程为 g ( u ) = m a x { f ( v i ) + h ( v j ) + ∑ v i ≠ v j ≠ v k g ( v k ) } = m a x { a ( v i ) + h ( v j ) + ∑ v j ≠ v k g ( v k ) } g(u)=max{f(v_i)+h(v_j)+sum_{v_ine v_j ne v_k }{g(v_k)}}=max{a(v_i)+h(v_j)+sum_{v_j ne v_k }{g(v_k)}} g(u)=max{f(vi​)+h(vj​)+∑vi​​=vj​​=vk​​g(vk​)}=max{a(vi​)+h(vj​)+∑vj​​=vk​​g(vk​)}。然后这个式子如果要枚举则要$O(n^2)$的时间复杂度，我们可以再优化，我们的$a(v_i)$必然是取最大值，那么就一直取最大值，而$h(v_j)$就一直枚举。当枚举到$v_i=v_j$时，我们的$a$取第二大值即可。也就是说，我们枚举哪个点是只走一步就掉头的点，掉头前往$t=3$的存在最多蝴蝶的点，然后再在这个点一路往下跑。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
// Good Good Study, Day Day AC.
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <cstring>
#include <math.h>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <map>
#include <algorithm> 
#include <unordered_map>
#include <unordered_set>
#define ffor(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define rrep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define PII pair<int,int>
#define int long long

using namespace std;

const int N = 1e5 + 5;
int n, T;
int f[N], g[N], h[N];
int a[N], t[N];

vector<int> ma[N];

void ready()
{
	IOS;
	cin >> T;
}

void dfs(int u, int fa) {
	int max1 = 0, max2 = 0, maxa=0;
	int res = 0;
	for (auto v : ma[u]) {
		if (v == fa) continue;
		dfs(v, u);
	}
	for (auto v : ma[u]) {
		if (v == fa) continue;
		res += g[v];
		maxa = max(maxa, a[v]);
	}
	h[u] = a[u] + res;
	g[u] = maxa + res;
	for (auto v : ma[u]) {
		if (v == fa || t[v] != 3) continue;
		if (a[v] > max1) {
			max2 = max1;
			max1 = a[v];
		}
		else {
			max2 = max(max2, a[v]);
		}
	}
	for (auto v : ma[u]) {
		if (t[v] == 3 && a[v] == max1) {
			g[u] = max(g[u], max2 + h[v] + res - g[v]);
		}
		else {
			g[u] = max(g[u], max1 + h[v] + res - g[v]);
		}
	}
	f[u] = a[u] + g[u];
}

void work()
{
	cin >> n;
	ffor(i, 1, n) {
		a[i] = f[i] = g[i] = h[i] = t[i] = 0;
		ma[i].clear();
	}
	ffor(i, 1, n) cin >> a[i];
	ffor(i, 1, n) cin >> t[i];
	ffor(i, 1, n - 1) {
		int u; int v;
		cin >> u >> v;
		ma[u].push_back(v);
		ma[v].push_back(u);
	}
	dfs(1, 0);
	cout << f[1] << 'n';
}

signed main()
{
	ready();
	while(T--)
	  work();
	return 0;
}

总结，动态规划，不管是哪种动态规划，一定要找到状态，状态一定要包括了所有状态，然后推出状态转移方程。

最后

以上就是活泼钥匙最近收集整理的关于[树形DP] The 2021 ICPC Asia Nanjing Regional Contest H题的全部内容，更多相关[树形DP]内容请搜索靠谱客的其他文章。