Bài A - Codeforces Round #530 (Div.1)

Đề bài:
Bài A: Mitya có một cái cây có gốc gồm n đỉnh được đánh số từ 1 đến n, với gốc là đỉnh 1. Mỗi đỉnh v ban đầu có một số nguyên a(v)>=0 được viết trên đó. Với mỗi đỉnh v, Mitya phải tính s(v): tổng các giá trị được viết trên các đỉnh trên đường đi từ đỉnh v đến gốc, cũng như là h(v)- chiều sâu của đỉnh v, kí hiệu số đỉnh trên đường đi từ đỉnh v đến gốc. Rõ ràng s(1)=a(1) và h(1)=1.
  Sau đó Mitya xóa tất cả các số a(v), và đột nhiên anh ấy xóa luôn tất cả giá trị s(v) của các đỉnh và thậm chí cả chiều sâu (đỉnh với chiều sâu h(v)). Nhiệm vụ của bạn là phục hồi lại tất cả các giá trị a(v) ở mỗi đỉnh, hoặc xác định rằng Mitya đã tạo ra sai lầm. Trong trường hợp có nhiều cách để phục hồi các giá trị, bạn được yêu cầu tìm một cách sao cho tối thiểu được tổng của các a(v) của các đỉnh trên cây.
Đầu vào:
+ Dòng đầu tiên chứa số n - số đỉnh của cây (2<=n<=10^5)
+ Dòng đầu tiên chứa các số nguyên p(1),p(2),...,p(n), với p(i) đại diện cho ba mẹ của đỉnh với chỉ số i trên cây (1<=p(i)<=i).
+ Dòng cuối cùng chứa các số nguyên s(1),s(2),...,s(n) (-1<=s(v)<=10^9), các giá trị được xóa thay bằng -1.
Đầu ra:
+ In ra một số nguyên  - tổng nhỏ nhất của tất cả các giá trị a(v) ở cây gốc, hoặc -1 nếu không tồn tại cây như vậy.
Ví dụ:
Đầu vào:
5
1 1 1 1
1 -1 -1 -1 -1
Đầu ra:
1
/**/
Đầu vào:
5
1 2 3 1
1 -1 2 -1 -1
Đầu ra:
2
/**/
Đầu vào:
3
1 2
2 -1 1
Đầu ra:
-1
Hướng dẫn:
 Để đạt được tổng nhỏ nhất có thể các giá trị cảu cây, với mỗi đỉnh với chiều sâu chẵn chúng ta cần đặt số 0 ở mỗi lá và giá trị lớn nhất có thể với mỗi đỉnh, bởi vì tăng giá trị không làm cho tổng kết quả tệ hơn - con cái chúng ta sẽ bù đắp cho nó. Bởi vì a(v)>=0, rõ ràng rằng: s(p(v))<=s(p(v))+a(v)=s(v). Với mỗi đứa trẻ u của đỉnh v nó cũng đúng rằng s(v)<=s(u).
Lời giải:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
const ll inf=1e9+1;
int s[N],p[N];
int main(){
 int n;
 scanf("%d",&n);
 for(int i=2;i<=n;i++)scanf("%d",&p[i]);
 for(int i=1;i<=n;i++){
  scanf("%d",&s[i]);
  if(s[i]==-1)s[i]=inf;
  s[p[i]]=min(s[p[i]],s[i]);
 }
 int mark=0;
 ll ans=0;
 for(int i=1;i<=n;i++){
  if(s[i]==inf)s[i]=s[p[i]];
  else if(s[i]<s[p[i]])mark=1;
  if(mark)break;
  ans+=s[i]-s[p[i]];
 }
 if(mark)printf("-1\n");
 else printf("%I64d\n",ans);
}