[普及/提高-]A105546.路径覆盖

题意

原题题意足够清晰，这里不在重述。

思路

注意到本题求代价最小，考虑 DP。

设 $dp_i$ 为根节点为 $i$ 的子树，通过染色使其叶子结点到该根节点的路径上至少有一个黑色结点的最小代价。

很明显，当节点 $i$ 是叶子节点时，只能修改自身以实现目的，顾花费为 $c_i$。

若节点 $i$ 不是根节点，那么有两种方案：
1.将自己染色，这样的话自己所有的叶子结点路径上一定会遇到自己这个黑色的节点，花费 $c_i$
2.将任务交给自己的子树，求自己子树满足条件的最小花费的总和。

显然取两种方案的最小值。

顾非叶子结点的转移方程是：

$$dp_u = \begin{cases} c_u, & \text{若 } u \text{ 是叶子节点} \\ \min\left(c_u, \sum\limits_{v \in \text{children}(u)} dp_v\right), & \text{否则} \end{cases}$$

其中 $\text{children}(u)$ 表示节点 $u$ 其儿子结点。

实现

深搜+动态规划，从根节点 $1$ 开始，不断往下搜，若发现该节点为叶子结点，即该节点没有任何儿子节点，那么直接将其赋值 $c_i$ 后回溯，在回溯途中计算根节点价值。

AC code

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
#define int long long 
int n , dp[N] , a[N];
vector<int> way[N];
void dfs(int now){
	if(way[now].size() == 0){
		dp[now] = a[now];
		return;
	}
	int tot = 0;
	dp[now] = a[now];
	for(auto i : way[now]){
		dfs(i);
		tot += dp[i];
	}
	dp[now] = min(dp[now] , tot);
}
signed main(){
	cin >> n;
	int x;
	for(int i = 2;i <= n;i ++){
		cin >> x;
		way[x].push_back(i);
	}
	for(int i = 1;i <= n;i ++){
		cin >> a[i];
	}
	dfs(1);
	cout << dp[1];
	return 0;
}