1098A - Sum in the tree(贪心、树)

A. Sum in the tree
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Mitya has a rooted tree with n
vertices indexed from 1 to n, where the root has index 1. Each vertex v initially had an integer number av≥0 written on it. For every vertex v Mitya has computed sv: the sum of all values written on the vertices on the path from vertex v to the root, as well as hv — the depth of vertex v, which denotes the number of vertices on the path from vertex v to the root. Clearly, s1=a1 and h1=1

.

Then Mitya erased all numbers av
, and by accident he also erased all values sv for vertices with even depth (vertices with even hv). Your task is to restore the values av for every vertex, or determine that Mitya made a mistake. In case there are multiple ways to restore the values, you’re required to find one which minimizes the total sum of values av

for all vertices in the tree.
Input

The first line contains one integer n
— the number of vertices in the tree (2≤n≤105). The following line contains integers p2, p3, … pn, where pi stands for the parent of vertex with index i in the tree (1≤pi<i). The last line contains integer values s1, s2, …, sn (−1≤sv≤109), where erased values are replaced by −1

.
Output

Output one integer — the minimum total sum of all values av
in the original tree, or −1 if such tree does not exist.

思路:给出了我们Si,要我们求出使所有Vi的和最小的sum,想一想就能明白,让一个Vi尽可能的去给更多的Si做贡献,即可使总的sum最小,故对每个-1的Si dfs求出其孩子中的最小Si(因为要求每个子Si总会大于父Si),最后判断如果有子Si<父Si,则输出-1。

Code:

#include<iostream>
#include<string>
#include<map>
#include<algorithm>
#include<memory.h>
#include<cmath>
#include<queue>
#include<sstream>
#define pii pair<int,int>
#define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
const int Max = 2e5 + 5;
int lst[Max];

int u[Max], v[Max], w[Max];
int first[Max], nex[Max], f[Max];
int g = 0;
ll s[Max];

void add(int a, int b)
{
   
	u[++g] = a;
	v[g] = b;
	nex[g] = first[a];
	first[a] = g;
}



ll dfs(int n)
{
   
	if (s[n]!=-1)
	{
   
		//v[n] = s[n] - s[f[n]];
		return s[n];
	}
	else
	{
   
		int k = first[n];ll mi = 1e9+5;
		while (k != -1)
		{
   
			mi = min(dfs(v[k]), mi);
			k = nex[k];
		}
		s[n] = mi;
		return s[n];
	}
}

int main()
{
   
	FAST;
	int n;cin >> n;
	memset(first, -1, sizeof(first));
	for (int i = 2;i <= n;i++)
	{
   
		int t;cin >> t;
		add(t, i);f[i] = t;
	}
	for (int i = 1;i <= n;i++)cin >> s[i];
	ll ans = 0;int flag = 0;
	for (int i = 1;i <= n;i++)
	{
   
		dfs(i);dfs(f[i]);
		if (dfs(i) == 1e9+5)ans += 0;//后面Si全是-1则令该点权为0
		else
		{
   
			if (dfs(f[i]) > dfs(i))flag = 1;
			ans += (dfs(i) - dfs(f[i]));
		}
	}
	if (flag)cout << -1 << endl;
	else cout << ans << endl;

}
全部评论

相关推荐

我是没经验的毕业生,这啥情况啊会不会是hr在刷kpi
JamesGosli...:字节boss属于是群发了,我都快入职字节了,其他部门还在和我boss打招呼
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
07-03 18:22
投了几百份简历,专业和方向完全对口,都已读不回。尝试改了一下学校,果然有奇效。
steelhead:这不是很正常嘛,BOSS好的是即便是你学院本可能都会和聊几句,牛客上学院本机会很少了
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务