题目描述
在一个树形结构的区域中安装监控设备，每个节点安装监控都有一定的成本。要求如果某个节点不安装监控，则其所有相邻节点必须安装监控。求覆盖整个树形区域的最小成本。
输入格式
第一行包含一个整数 n，表示树中节点的数量。
第二行包含 n 个整数，表示每个节点安装监控的成本。
接下来 n-1 行，每行包含两个整数 u 和 v，表示树中的一条边。
输出格式
输出一个整数，表示最小总成本。
样例输入
输入样例 Input
5 1 2 3 4 5 1 2 1 3 2 4 2 5
样例输出
输出样例 Output
4
解决方案
使用树形动态规划（DP）解决此问题：
状态定义
- 设 dp[i][0] 表示不在节点 i 安装监控的最小成本
- 设 dp[i][1] 表示在节点 i 安装监控的最小成本
状态转移
- 如果节点 i 不安装监控，则其所有子节点必须安装监控
- 如果节点 i 安装监控，则其子节点可以安装也可以不安装
转移方程
- dp[u][0] = Σ dp[v][1] (v是u的子节点)
- dp[u][1] = cost[u] + Σ min(dp[v][0], dp[v][1]) (v是u的子节点)
核心代码
C++ 代码 C++
#include<bits/stdc++.h>
using namespace std;
int n, a[323232], dp[323232][2];
vector<int> e[323232];
inline void dfs(int x, int fa) {
for(int i = 0; i < (int)e[x].size(); i++) {
if(e[x][i] == fa) continue;
dfs(e[x][i], x);
dp[x][0] += dp[e[x][i]][1];
dp[x][1] += min(dp[e[x][i]][0], dp[e[x][i]][1]);
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for(int i = 1; i <= n; i++) cin >> dp[i][1];
for(int i = 1, u, v; i < n; i++) {
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
dfs(1, -1);
cout << min(dp[1][1], dp[1][0]);
return 0;
}算法复杂度
时间复杂度：O(n)，其中 n 是节点数量，因为每个节点只需访问一次。
空间复杂度：O(n)，用于存储树结构和DP数组。