题目描述
输入格式
第一行包含一个整数 n。
第二行包含 n−1 个整数 p2,p3,…,pn，其中 pi 表示节点 i 的父节点编号。
第三行包含 n 个整数 s1,s2,…,sn，注意，由于所有 h 值为偶数的节点的 s 值都是未知的，所以这些节点的 s 值并未直接给出，而是用 −1 来代替。
输出格式
一个整数，表示 ∑ i = 1 n a i 的最小可能值。
如果不存在任何满足已知信息的合理赋值方案，则输出 −1。
数据范围
前 4 个测试点满足 2≤n≤5。
所有测试点满足 2≤n≤105，1≤pi
输入样例1：
5
1 1 1 1
1 -1 -1 -1 -1
输出样例1：
1
输入样例2：
5
1 2 3 1
1 -1 2 -1 -1
输出样例2：
2
输入样例3：
3
1 2
2 -1 1
输出样例3：
-1
思路
容易知道，从根节点向下会交替经过奇偶节点。
而对于奇节点有固定值，那么对于每个偶节点，其所有出点都是奇节点，会限制该偶节点的值，贪心的选择最小的出点值，并且在偶数层，确定完该偶数节点值后，出点的值也都一并确定了。
代码
#include <iostream> #include <cstring> #include <algorithm> using namespace std; #define int long long const int N = 1000100, M = N << 1; int dep[N]; int h[N], e[M], ne[M], idx; int n; int a[N], b[N]; bool flag = true; void add(int a, int b) // 添加一条边a->b { e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; } void dfs(int u, int f, int now) { if(!flag) return ; dep[u] = dep[f] + 1; if(dep[u] % 2 == 0) { int r = 1e17; for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; int x = a[j]; if(j == f) continue; if(x < now) flag = false; r = min(r, x); } b[u] = r == 1e17 ? 0 : r - now; for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if(j == f) continue; b[j] = a[j] - b[u] - now; } } for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if(j == f) continue; dfs(j, u, now + b[u]); } } signed main() { memset(h, -1, sizeof h); cin >> n; for (int i = 2; i <= n; i++) { int x; cin >> x; add(x, i); add(i, x); } for (int i = 1; i <= n; i++) cin >> a[i]; b[1] = a[1]; dfs(1, 0, 0); if(!flag) cout << -1 << endl; else { int ans = 0; for (int i = 1; i <= n; i++) ans += b[i]; cout << ans << endl; } return 0; }
