City Upgrading

The city where crazyzhk resides is structured as a tree. On a certain day, the city’s network needs to be upgraded. To achieve this goal, routers need to be deployed. Each router covers the node it is placed on and its neighboring nodes. There is a cost $ a_i $ associated with placing a router at each node. The question is: How can the routers be deployed at minimum cost to ensure that every node is covered?

题目大意

crazyzhk 所居住的城市被构建成一棵树。在某一天，城市的网络需要升级。为了实现这个目标，需要部署路由器。每个路由器覆盖其所放置的节点及其相邻节点。在每个节点放置路由器都有一个成本 $a_i$。问题是：如何以最小成本部署路由器，以确保每个节点都被覆盖？

题目思路

每一个点可以由自己照亮，也可以由相邻的点照亮，在照亮该点的所有方案中选一个最小的方案。已知这是一颗树，考虑树形 DP。点被照亮一共由三种可能的情况：

  • 自己点亮自己
  • 被儿子点亮
  • 被父亲点亮

由此可以设出状态, u 表示当前点:

  • dp[u][0] 表示自己点亮的 cost
  • dp[u][1] 表示被儿子点亮的 cost
  • dp[u][2] 表示被父亲点亮的 cost

思考状态转移：

对于自己点亮的情况，dp[u][0] = w[u],遍历子节点时，加上每个子节点点亮的最小花费即可

假设当前点是被父亲点亮的，这种情况下，当前点无法对子节点提供帮助，只能让子节点自立更生或者子节点被自己的儿子点亮。

假设当前点是被自己的儿子点亮，在之前假设当前点是被父亲点亮点亮时，我们统计了子节点自立更生或者子节点被自己的儿子点亮的最小花费总和。对于这种情况，只需要选定一个子节点点亮，并将这个子节点的花费改为子节点被自己点亮即可。

code

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 200010;

int n, dp[N][3], h[N], w[N], cnt;

struct E {
	int to, nxt;
} e[N << 1];

void add(int a, int b) {
	e[cnt].to = b;
	e[cnt].nxt = h[a];
	h[a] = cnt++;
}

void dfs(int u, int f) {
	// dp[u][0] 自己
	// dp[u][1] 儿子
	// dp[u][2] 爹
	dp[u][0] = w[u];
	int res = 0;
	for(int i = h[u]; ~i; i = e[i].nxt) {
		int j = e[i].to;
		if(j == f) continue;
		dfs(j, u);
		dp[u][0] += min({dp[j][0], dp[j][1], dp[j][2]});
		dp[u][2] += min(dp[j][0], dp[j][1]);
		res += min(dp[j][0], dp[j][1]);
	}
	// cout << res << endl;
	dp[u][1] = 0x3f3f3f3f3f3f3f;
	for(int i = h[u]; ~i; i = e[i].nxt) {
		int j = e[i].to;
		if(j == f) continue;
		dp[u][1] = min(dp[u][1], res - min(dp[j][0], dp[j][1]) + dp[j][0]);
	}
}

void solve() {
	memset(dp, 0, sizeof dp);
	memset(h, -1, sizeof h);
	cnt = 0;
	scanf("%lld", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%lld", &w[i]);
	}
	for(int i = 1; i < n; i++) {
		int u, v;
		scanf("%lld %lld", &u, &v);
		add(u, v);
		add(v, u);
	}
	dfs(1, 0);
	printf("%lld\n", min({dp[1][0], dp[1][1]}));
}

signed main() {
	int T;
	scanf("%lld", &T);
	//cout << T << endl;
	while(T--) solve();
	return 0;
}