正文
Codeforces 1099 D. Sum in the tree-构造最小点权和有根树 贪心+DFS(Codeforces Round #530 (Div. 2))
小程序：扫一扫查出行【扫一扫了解最新限行尾号】
复制小程序
D. 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 nn vertices indexed from 11 to nn, where the root has index 11. Each vertex vv initially had an integer number av≥0av≥0 written on it. For every vertex vv Mitya has computed svsv: the sum of all values written on the vertices on the path from vertex vv to the root, as well as hvhv — the depth of vertex vv, which denotes the number of vertices on the path from vertex vv to the root. Clearly, s1=a1s1=a1 and h1=1h1=1.
Then Mitya erased all numbers avav, and by accident he also erased all values svsv for vertices with even depth (vertices with even hvhv). Your task is to restore the values avav 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 avav for all vertices in the tree.
Input
The first line contains one integer nn — the number of vertices in the tree (2≤n≤1052≤n≤105). The following line contains integers p2p2, p3p3, ... pnpn, where pipi stands for the parent of vertex with index ii in the tree (1≤pi<i1≤pi<i). The last line contains integer values s1s1, s2s2, ..., snsn (−1≤sv≤109−1≤sv≤109), where erased values are replaced by −1−1.
Output
Output one integer — the minimum total sum of all values avav in the original tree, or −1−1 if such tree does not exist.
Examples
input
Copy
5
1 1 1 1
1 -1 -1 -1 -1
output
Copy
1
input
Copy
5
1 2 3 1
1 -1 2 -1 -1
output
Copy
2
input
Copy
3
1 2
2 -1 1
output
Copy
-1
题意就是给你一个有根树，然后给你每个节点的父亲，然后给你每个节点到根节点的点权之和，然后就是偶数深度的节点的到根节点的点权之和被抹去了，是-1，让你将这个树还原，然后求出所有节点的最小点权之和。
因为是隔一层就断了，所以直接直接给偶数深度节点爸爸赋值他儿子的值中最小的那个，然后，儿子-爸爸的值算出每个点的点权，最后加起来就可以了。如果节点的值是负数，就是不满足条件的，直接-1输出就可以了。我写的时候，wa了好久，搞不清楚为什么，不用开long long吧，我不开会wa，然后就是如果一个节点是直接连接根节点的，他没有儿子，那么我们可以给他赋值为0，我这里写早了，写到dfs出来时每个节点的点权之前了，这样算出来的肯定是不对的，就是直接0-根节点的权值，肯定是错的，当时想的是算完之后再处理这些特殊的点，但是手抖写的时候写挫了，改了就过了。
代码:
//D
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const int maxn=2e5+; struct node{
int to,val,next;
}edge[maxn<<]; int head[maxn<<],dep[maxn],fa[maxn][],cnt;
int dis[maxn]; void add(int x,int y,int v){edge[++cnt].to=y,edge[cnt].val=v,edge[cnt].next=head[x],head[x]=cnt;}//存图 void dfs(int u,int fath)
{
dep[u]=dep[fath]+;
for(int i=head[u];i;i=edge[i].next){
int v=edge[i].to,w=edge[i].val;
if(v!=fath){
dis[v]=w;
if(dep[u]%==){
dis[u]=min(dis[u],dis[v]);//找子节点的值的最小值
}
}
}
for(int i=head[u];i;i=edge[i].next){
int v=edge[i].to,w=edge[i].val;
if(v!=fath){
dfs(v,u);
if(dis[v]!=inf)//如果不是特殊节点
dis[v]=dis[v]-dis[u];//当前点的点权就是自己-爸爸的
}
}
} int a[maxn],b[maxn]; int main()
{
int n;
cin>>n;
for(int i=;i<=n;i++)
cin>>a[i];
for(int i=;i<=n;i++){
cin>>b[i];
if(b[i]==-) b[i]=inf;
}
for(int i=;i<=n;i++){
add(a[i],i,b[i]);
add(i,a[i],b[i]);
}
dis[]=b[];
dfs(,);
for(int i=;i<=n;i++){
if(dis[i]==inf) dis[i]=;//如果是特殊节点，处理完还是没确定值的，就赋值为0
}
// for(int i=1;i<=n;i++)
// cout<<dis[i]<<endl;
ll ans=;
int flag=;
for(int i=;i<=n;i++){
if(dis[i]<){
flag=;break;
}
ans+=dis[i];
}
if(flag==) cout<<ans<<endl;
else cout<<-<<endl;
} /*
10
1 1 1 1 2 3 4 5 1
3 -1 -1 -1 -1 3 3 3 3 -1 3
*/
