题解 CF1099D 【Sum in the tree】

览遍千秋 · 2019-08-17 22:22:32 · 题解

本题解同步发布于本场\mathrm{CF}总题解，欢迎来踩。

A(DIV.1),D(DIV.2) - Sum in the tree

直观但错误的想法

一开始有一个非常直观的想法，对于每一个结点，如果不知道它的s，就直接设它为0，可是在\color{red} \mathrm{WA}了几次之后，就会考虑到这样的一种情况：

有一结点x，s未知，如果这时候令其点权为k，则其每一个儿子都可以比令x点权为0少掉k的代价，这种情况显然比直接令x优。

但是这个错误的思路可以打开我们正确的思路。

考虑无解

贪心即可。

code:

#include<bits/stdc++.h>
using namespace std;
#define maxn 100003
#define int long long
#define INF 0x3f3f3f3f
int n,fa[maxn];
int s[maxn],ans;
int Head[maxn],Next[maxn],tot,to[maxn];

template<typename Tp>
void read(Tp &x){
    x=0;char ch=1;int fh;
    while(ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();
    if(ch=='-'){
        ch=getchar();fh=-1;
    }
    else fh=1;
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    x*=fh;
}

void dfs1(int x){
    s[fa[x]]=min(s[fa[x]],s[x]);
    for(int i=Head[x];i;i=Next[i]){
        dfs1(to[i]);
    }
}

void dfs2(int x){
    if(s[x]<s[fa[x]]){
        puts("-1");exit(0);
    }
    if(s[x]!=INF)
        ans+=s[x]-s[fa[x]];
    for(int i=Head[x];i;i=Next[i]){
        dfs2(to[i]);
    }
}

void add(int x,int y){
    to[++tot]=y,Next[tot]=Head[x],Head[x]=tot;
}

int main(){
    read(n);
    for(register int i=2;i<=n;i++){
        read(fa[i]);
        add(fa[i],i);
    }
    for(register int i=1;i<=n;i++){
        read(s[i]);if(s[i]==-1) s[i]=INF;
    }
    dfs1(1);dfs2(1);
    printf("%I64d\n",ans);
    return 0;
}