# codeforces round 530 div2

Posted by 111qqz on Sunday, January 6, 2019

## TOC

A,B,C:都很简单，不说了。

D:一棵树，给出树的结构，以及从树根到某个深度为偶数的节点的路径和，问能否构造一种所有节点点权和最小的树，输出最小点权和。

``````#include <bits/stdc++.h>
#define PB push_back
#define fst first
#define sec second
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define ms(a,x) memset(a,x,sizeof(a))
typedef long long LL;
#define pi pair < int ,int >
#define MP make_pair

using namespace std;
const double eps = 1E-8;
const int dx4[4]={1,0,0,-1};
const int dy4[4]={0,-1,1,0};
const int inf = 0x3f3f3f3f;
const int N=1E5+7;
int n;
vector<int>edge[N];
int s[N];
int d[N];
bool vis[N];
int a[N];
// void dfs(int u,int dep)
// {
//     int siz = edge[u].size();
//     for (auto v: edge[u])
//     {
//         dfs(v,dep+1);
//     }
// }
int bfs()
{
ms(d,-1);
ms(vis,false);
queue<int>Q;
Q.push(1); //root
vis[1] = true;
d[1] = s[1];
while (!Q.empty())
{
int u = Q.front();Q.pop();
// cout<<"u:"<<u<<" "<<Q.size()<<endl;
int min_sum_in_leaf = inf;
bool even = false;
// cout<<"v seq:";
for ( auto v: edge[u])
{
// cout<<v<<" s[v]:"<<s[v]<<" ";
if (s[v]==-1)
{
Q.push(v);
d[v] = d[u];
even = true;
}
if (s[v]!=-1) min_sum_in_leaf = min(min_sum_in_leaf,s[v]);
}
cout<<endl;
if (even) continue;
// cout<<"min_sum_in_leaf:"<<min_sum_in_leaf<<endl;
// cout<<"u:"<<u<<" d[u]:"<<d[u]<<endl;
if (d[u]>min_sum_in_leaf) return -1; //不可能
if (min_sum_in_leaf==inf)
{
// a[u] =
continue;
}
a[u] = min_sum_in_leaf - d[u];
d[u] = min_sum_in_leaf;
for ( auto v: edge[u])
{
a[v] = s[v] - d[u];
d[v] = s[v];
// cout<<"v:"<<v<<" a[v]:"<<a[v]<<" d[v]:"<<d[v]<<endl;
Q.push(v);
}
}
return 0;
}
int main()
{
#ifndef  ONLINE_JUDGE
freopen("./in.txt","r",stdin);
#endif

cin>>n;
for ( int i = 2  ; i <= n ; i++)
{
int x;
cin>>x;
edge[x].push_back(i);
}
for ( int i = 1 ; i <= n ; i++) cin>>s[i];
//   for ( int i = 1 ;i <= n ; i++) cout<<"s[i]:"<<s[i]<<endl;
ms(a,0);
a[1] = s[1];
LL ans = bfs();
if (ans==-1)
{
puts("-1");

}
else
{
for ( int i = 1 ; i <= n ; i++)
{
//   cout<<i<<":"<<a[i]<<" d:"<<d[i]<<" s:"<<s[i]<<endl;
ans = ans + a[i];
}
cout<<ans<<endl;
}

#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}
``````