codeforces round 530 div2
A,B,C:都很简单，不说了。
D:一棵树，给出树的结构，以及从树根到某个深度为偶数的节点的路径和，问能否构造一种所有节点点权和最小的树，输出最小点权和。
思路：
容易知道，如果想要点权和最小，那么尽可能让靠近树根的点承担更多的点权。
具体做法是，bfs，对于每个节点u，取其儿子中最小的S值求节点u的信息。
比赛的时候wa16...最后发现是答案要用long long存...因为单个路径和是<=1E9的。。多个加起来会超过int... 长时间不打连这种常见的坑都不敏感了啊。。。
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
1using namespace std;
2const double eps = 1E-8;
3const int dx4[4]={1,0,0,-1};
4const int dy4[4]={0,-1,1,0};
5const int inf = 0x3f3f3f3f;
6const int N=1E5+7;
7int n;
8vector<int>edge[N];
9int s[N];
10int d[N];
11bool vis[N];
12int a[N];
13// void dfs(int u,int dep)
14// {
15// int siz = edge[u].size();
16// for (auto v: edge[u])
17// {
18// dfs(v,dep+1);
19// }
20// }
21int bfs()
22{
23 ms(d,-1);
24 ms(vis,false);
25 queue<int>Q;
26 Q.push(1); //root
27 vis[1] = true;
28 d[1] = s[1];
29 while (!Q.empty())
30 {
31 int u = Q.front();Q.pop();
32 // cout<<"u:"<<u<<" "<<Q.size()<<endl;
33 int min_sum_in_leaf = inf;
34 bool even = false;
35 // cout<<"v seq:";
36 for ( auto v: edge[u])
37 {
38 // cout<<v<<" s[v]:"<<s[v]<<" ";
39 if (s[v]==-1)
40 {
41 Q.push(v);
42 d[v] = d[u];
43 even = true;
44 }
45 if (s[v]!=-1) min_sum_in_leaf = min(min_sum_in_leaf,s[v]);
46 }
47 cout<<endl;
48 if (even) continue;
49 // cout<<"min_sum_in_leaf:"<<min_sum_in_leaf<<endl;
50 // cout<<"u:"<<u<<" d[u]:"<<d[u]<<endl;
51 if (d[u]>min_sum_in_leaf) return -1; //不可能
52 if (min_sum_in_leaf==inf)
53 {
54 // a[u] =
55 continue;
56 }
57 a[u] = min_sum_in_leaf - d[u];
58 d[u] = min_sum_in_leaf;
59 for ( auto v: edge[u])
60 {
61 a[v] = s[v] - d[u];
62 d[v] = s[v];
63 // cout<<"v:"<<v<<" a[v]:"<<a[v]<<" d[v]:"<<d[v]<<endl;
64 Q.push(v);
65 }
66 }
67 return 0;
68}
69int main()
70{
71 #ifndef ONLINE_JUDGE
72 freopen("./in.txt","r",stdin);
73 #endif
1 cin>>n;
2 for ( int i = 2 ; i <= n ; i++)
3 {
4 int x;
5 cin>>x;
6 edge[x].push_back(i);
7 }
8 for ( int i = 1 ; i <= n ; i++) cin>>s[i];
9// for ( int i = 1 ;i <= n ; i++) cout<<"s[i]:"<<s[i]<<endl;
10 ms(a,0);
11 a[1] = s[1];
12 LL ans = bfs();
13 if (ans==-1)
14 {
15 puts("-1");
1 }
2 else
3 {
4 for ( int i = 1 ; i <= n ; i++)
5 {
6 // cout<<i<<":"<<a[i]<<" d:"<<d[i]<<" s:"<<s[i]<<endl;
7 ans = ans + a[i];
8 }
9 cout<<ans<<endl;
10 }
1 #ifndef ONLINE_JUDGE
2 fclose(stdin);
3 #endif
4 return 0;
5}