CF1098A Sum in the tree（贪心）

满分做法：

由题：s[u]<=s[v]（u是v的父亲）,因为a[i]是非负的。此时点u和他儿子的点权和为：

(sleft[ u ight] +sum_{vin sonleft( u ight)}{(sleft[ v ight] -sleft[ u ight])})

(=left( 1-cntleft( u ight) ight) *sleft[ u ight] +sum_{vin sonleft( u ight)}{s}left[ v ight])；

(k=left( 1-cntleft( u ight) ight) le 0)。

所以(s[u])越大点权和越小，最优的(s[u]=min(s[v]));对于s[i]为-1的点，我们先把他赋成较大的数，再通过他们的儿子对他进行赋值。而对于没有被更改的点（也就是偶数层的叶子结点），我们就令他为(0)保证答案最优.

#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
typedef long long ll;
const int maxm=1e5+7;
int n;
ll ans;
int f[maxm];
ll s[maxm];
int main()
{
 scanf("%d",&n);
 for(int i=2;i<=n;i++)
 scanf("%d",&f[i]);
 for(int i=1;i<=n;i++)
 {
  scanf("%lld",&s[i]);
  if(s[i]==-1) s[i]=2147483647;
 }
 for(int i=2;i<=n;i++)
 s[f[i]]=min(s[i],s[f[i]]);
 for(int i=1;i<=n;i++)
 {
  if(s[i]<s[f[i]])
  {
   printf("-1
");
   return 0;
  }
  if(s[i]<2147483647) ans+=s[i]-s[f[i]];
 }
 printf("%lld
",ans);
 return 0;	
}