洛谷P14919[GESP202512 六级] 路径覆盖

依旧题目传送门……
讲实话，当我看到这题的标签时，吓了一大跳（OS：CCF还是太阴了）
废话不多说，直接讲正解

---

正解

首先，当第i个节点为叶子节点时，代价肯定是c[i]的。

那么，我们遍又双又叕便可知道第i个节点有very多个节点时，代价最小肯定是c[i]与他的所有孩子的最小代价加起来进行取最小值的。

AC代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
vector<int> v[100010];
int n, c[100010];
int dfs(int x){if(v[x].empty()) return c[x];int ans = 0;for(int i = 0; i < v[x].size(); i++) ans += dfs(v[x][i]);return min(ans, c[x]);
}
signed main(){cin >> n;for(int i = 2; i <= n; i++){int f;cin >> f;v[f].push_back(i);}for(int i = 1; i <= n; i++) cin >> c[i];cout << dfs(1);
}