思路:
从上到下层次遍历,对于偶数层节点,以$v$为例,令它的权值$a[v]=\min_u{s[u]}-s[fa[v]]$,其中$u$是$v$的子节点。对于奇数层节点$r$,它的权值等于$s[r]-s[fa[r]]$,由于层次遍历的顺序性,$fa[r]$一定是偶数层节点,而$a[fa[r]]、s[fa[r]]$在上一层已确定。
这样分配权值可以保证答案全局最优。
贪心证明:
假设存在点$a$,$a$的子节点有$b_1、b_2、b_3$(简单以三个点证明,推广到$n$个也一样)
有$a+b_1=k_1$、$a+b_2=k_2$、$a+b_3=k_3$
那么$a+b_1+b_2+b_3=k_1+k_2+k_3-2a$
所以令 $a$ 最大,就可以使$a+b_1+b_2+b_3$最小。
根据三个等式知$a$最大应该取为$\min_i{k_i}$
附:如果不加以思考一下,可能不理解这个证明有什么用…
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int fa[N], s[N], a[N];
int h[N], e[N], ne[N], idx;
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
int main()
{
memset(h, -1, sizeof h);
int n, x;
scanf("%d", &n);
add(0, 1);
for(int i = 2; i <= n; i++) {
scanf("%d", &x);
fa[i] = x;
add(x, i);
}
for(int i = 1; i <= n; i++) scanf("%d", &s[i]);
queue<int> q;
q.push(1);
int level = 1;
LL ans = 0;
a[1] = s[1];
bool flag = true;
while(q.size()) {
int len = q.size();
level++;
while(len--) {
int ver = q.front(), minval = 2e9;
q.pop();
for(int i = h[ver]; ~i; i = ne[i]) {
int j = e[i];
q.push(j);
if(level % 2 == 1) {
minval = min(minval, s[j]);
}
}
if(level % 2 == 1) {
if(minval == 2e9) continue;
a[ver] = minval - s[fa[ver]];
s[ver] = minval;
} else {
a[ver] = s[ver] - s[fa[ver]];
}
if(a[ver] < 0) {
flag = false;
break;
}
ans += a[ver];
}
if(!flag) {
ans = -1;
break;
}
}
printf("%lld", ans);
return 0;
}