Codeforces Round #530 (Div. 2) D. Sum in the tree 树上贪心

D. Sum in the tree

题意

给出一颗树，奇数层数的点有值，值代表从1到该点的简单路的权值的和，偶数层数的点权值被擦去了 问所有节点的和的最小可能是多少

思路

对于每一个-1（也就是值未知的点）其所填的值的最小值小于等于他的自己点中已知的点的权值 换个说法就是 一个-1点有多个子树 那么这个点的值最小也是这几个子树里面的最大的值，才能使得其合法 从根节点递归求值即可

其中注意 这里计算权值和的时候,因为已知每个点到根节点的路径的点的权值和所以计算一个节点以及其子树到根节点的权值和的，等于这个节点的每个子节点的树到根节点的权值和的和减去这一个点可以取得的最小值*(支路数-1) 也就相当于一个容斥关系

ps:当时我是怎么写出那么毒瘤的代码的。。。

#include<bits/stdc++.h>

using namespace std;

const int maxn = 3e5+5;

typedef long long ll;

#define F first

#define S second

#define pb push_back

#define pii pair<int ,int >

#define mkp make_pair

#define int long long

const int inf=0x3f3f3f3f;

int head[maxn];

int s[maxn];

int size=0;

struct Node{

	int to,next;

}edge[maxn];

void add(int x,int y){

	edge[size].to=y;

	edge[size].next=head[x];

	head[x]=size++;

}

int ans=0;

int ok=1;

pair<int,int>  dfs(int x,int fa,int nowmax){

	int sum=0;

	int cnt=0;

	int minnum=0x3f3f3f3f;

	for(int i=head[x];i!=-1;i=edge[i].next){

		int y=edge[i].to;

		if(fa!=y){

			cnt++;

			if(nowmax>s[y]&&s[y]!=-1){

				printf("-1\n");

				ok=0;

				return mkp(-1,-1);

			}

			 pii tmp=dfs(y,x,max(nowmax,s[y]));

			 sum+=tmp.F;

			 minnum=min(minnum,tmp.S);

		}

	}

//	cout<<x<<" "<<sum<<" "<<nowmax<<" "<<minnum<<endl;

	if(cnt==0)return mkp(nowmax,nowmax);

	return mkp(sum-(cnt-1)*minnum,nowmax);

}

int32_t main(){

	int n;

	scanf("%lld",&n);

	int tmp;

	memset(head,-1,sizeof(head));

	size=0;

	for(int i=2;i<=n;i++){

		scanf("%lld",&tmp);

		add(tmp,i);

	}

	for(int i=1;i<=n;i++){

		scanf("%lld",&s[i]);

	}

	int num=dfs(1,-233,s[1]).F;

	if(ok)cout<<num<<endl;

	return 0;

}