codeforces round 530 div2

  1#include <bits/stdc++.h>
  2#define PB push_back
  3#define fst first
  4#define sec second
  5#define lson l,m,rt<<1
  6#define rson m+1,r,rt<<1|1
  7#define ms(a,x) memset(a,x,sizeof(a))
  8typedef long long LL;
  9#define pi pair < int ,int >
 10#define MP make_pair
 11
 12using namespace std;
 13const double eps = 1E-8;
 14const int dx4[4]={1,0,0,-1};
 15const int dy4[4]={0,-1,1,0};
 16const int inf = 0x3f3f3f3f;
 17const int N=1E5+7;
 18int n;
 19vector<int>edge[N];
 20int s[N];
 21int d[N];
 22bool vis[N];
 23int a[N];
 24// void dfs(int u,int dep)
 25// {
 26//     int siz = edge[u].size();
 27//     for (auto v: edge[u])
 28//     {
 29//         dfs(v,dep+1);
 30//     }
 31// }
 32int bfs()
 33{
 34    ms(d,-1);
 35    ms(vis,false);
 36    queue<int>Q;
 37    Q.push(1); //root
 38    vis[1] = true;
 39    d[1] = s[1];
 40    while (!Q.empty())
 41    {
 42        int u = Q.front();Q.pop();
 43        // cout<<"u:"<<u<<" "<<Q.size()<<endl;
 44        int min_sum_in_leaf = inf;
 45        bool even = false;
 46        // cout<<"v seq:";
 47        for ( auto v: edge[u])
 48        {
 49            // cout<<v<<" s[v]:"<<s[v]<<" ";
 50            if (s[v]==-1)
 51            {
 52                Q.push(v);
 53                d[v] = d[u];
 54                even = true;
 55            }
 56            if (s[v]!=-1) min_sum_in_leaf = min(min_sum_in_leaf,s[v]);
 57        }
 58        cout<<endl;
 59        if (even) continue;
 60        // cout<<"min_sum_in_leaf:"<<min_sum_in_leaf<<endl;
 61        // cout<<"u:"<<u<<" d[u]:"<<d[u]<<endl;
 62        if (d[u]>min_sum_in_leaf) return -1; //不可能
 63        if (min_sum_in_leaf==inf)
 64        {
 65            // a[u] = 
 66            continue;
 67        }
 68        a[u] = min_sum_in_leaf - d[u];
 69        d[u] = min_sum_in_leaf;
 70        for ( auto v: edge[u])
 71        {
 72            a[v] = s[v] - d[u];
 73            d[v] = s[v];
 74            // cout<<"v:"<<v<<" a[v]:"<<a[v]<<" d[v]:"<<d[v]<<endl;
 75            Q.push(v);
 76        }
 77    }
 78    return 0;
 79}
 80int main()
 81{
 82    #ifndef  ONLINE_JUDGE 
 83    freopen("./in.txt","r",stdin);
 84  #endif
 85
 86  cin>>n;
 87  for ( int i = 2  ; i <= n ; i++)
 88  {
 89      int x;
 90      cin>>x;
 91      edge[x].push_back(i);
 92  }
 93  for ( int i = 1 ; i <= n ; i++) cin>>s[i];
 94//   for ( int i = 1 ;i <= n ; i++) cout<<"s[i]:"<<s[i]<<endl;
 95  ms(a,0);
 96  a[1] = s[1];
 97  LL ans = bfs();
 98  if (ans==-1)
 99  {
100      puts("-1");
101
102  }
103  else
104  {
105      for ( int i = 1 ; i <= n ; i++)
106      {
107        //   cout<<i<<":"<<a[i]<<" d:"<<d[i]<<" s:"<<s[i]<<endl;
108          ans = ans + a[i];
109      } 
110      cout<<ans<<endl;
111  }
112
113
114
115
116
117  #ifndef ONLINE_JUDGE  
118  fclose(stdin);
119  #endif
120    return 0;
121}