D. Sum in the tree
题目链接：https://codeforces.com/contest/1099/problem/D
题意：
给出一棵树，以及每个点的si，这里的si代表从i号结点到根节点的权值和。但是有些si=-1，这就相当于丢失了当前结点的数据。
假设原本每个点的权值为ai，那么现在求sum{ai}的最小为多少，ai为非负数。
题解：
这题可以单独看每一条链上的s值，假设当前结点为u，儿子结点v，那么就有几种情况：
1.su==-1&&sv==-1，这种不用管，继续往下看；
2.su==-1&&sv>=0，这种情况，su以及上面可能有多个si为-1的结点，但这里我们可以就把它看作一个点，然后找到非-1父亲结点的s值，假设为p，那么sv-sp就是中间结点的权值和，看作一个点的话，就是那个点的a值，同时根据这个我们可以计算出其sum值。至于这里怎么求sp，可以在dfs的时候记录一下。
3.su>=0&&sv==-1，这里就需要上面的记录了，记录目前的su值，方便后面找sp；
4.su>=0&&sv>=0，这里直接往下搜索就行了。
结合上面的分析，我们只需要一个dfs记录一下就好了，最后求au的时候就是sumu-sump，也可以在dfs的过程中处理。
但是我们刚才只是对链的分析，一个结点可能有多个儿子结点。想一下，会发现只有上面第2种情况会多考虑一点，因为根据哪个儿子结点来确定当前的s是一个问题。
这个问题也不难解决，取min{sv-sp}即可，一方面是让其尽量大，另一方面是保证方案可行。
最后再判断一下可行性就行了。
代码如下：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5+;
int n;
vector <int> g[N];
ll sum[N],b[N];
int flag = ;
void dfs(int u,ll a,int fa){
int son = ;
if(flag) return ;
int f=;
for(auto v:g[u]){
if(v==fa) continue ;
if((sum[u]==- && sum[v]>=) ||f){
f=;
ll now=sum[v]-a;
if(sum[u]==-) sum[u]=now+a;
if(sum[u]!=-) sum[u]=min(sum[u],now+a);
}
}
for(auto v:g[u]){
if(v==fa) continue ;
son++;
if(sum[v]==- && sum[u]==-){
dfs(v,a,u);
continue ;
}
dfs(v,sum[u],u);
}
if(son==&&sum[u]==-){
b[u]=;
return ;
}
if(sum[u]!=-) b[u]=sum[u]-a;
}
int main(){
cin>>n;
for(int i=;i<=n;i++){
int f;
scanf("%d",&f);
g[f].push_back(i);
g[i].push_back(f);
}
for(int i=;i<=n;i++) scanf("%I64d",&sum[i]);
if(sum[]==-) sum[]=;
dfs(,,-);
for(int i=;i<=n;i++){
if(b[i]<) flag=;
}
if(flag) puts("-1");
else{
ll ans = ;
for(int i=;i<=n;i++) ans+=b[i];
cout<<ans;
}
return ;
}
/*
7
1
2
1
4 4 5
0 -1 3 -1 -1 3 -1
*/