Codeforces #530 (Div. 1) A. Sum in the tree(遞推 貪心)

題目連接配接: https://codeforces.com/problemset/problem/1098/A

題目大意: 給你一顆有根樹和奇數層高的結點到根結點的點權之和,求最小的點權和

題目保證了給先出結點的一定時後面結點的兄弟或者祖先,是以我們能可以直接選擇遞推

特判根結點,他的點權就是s[1]

對結點i,如果他的s[i]=-1 要使所有點權和最小,那麼s[i]=min(s[j]) j是i的兒子結點 ans[i] = s[k]-s[i] k是i的父親結點 如果ans[i]<0 說明無解

如果s[i]!=-1 那麼 ans[i]=s[k]-s[i] 判斷ans[i]是否小于0

k和j在輸入的時候就能處理好,然後遞推就完事了

#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<stdlib.h>
#include<algorithm>
#include<time.h>
#include<unordered_map>
#define bug1(g) cout<<"test: "<<g<<endl
#define bug2(g,i) cout<<"test: "<<g<<" "<<i<<endl
#define bug3(g,i,k) cout<<"test: "<<g<<" "<<i<<" "<<k<<endl
#define bug4(a,g,i,k) cout<<"test: "<<a<<" "<<g<<" "<<i<<" "<<k<<endl
using namespace std;
typedef long long ll;
int n;
vector<int>a[100005];
int s[100005],h[100005],la[100005];
int ans[100005];
int main()
{
    ios::sync_with_stdio(0);
    cin>>n;
    int x;
    for(int i =2;i<=n;i++)
    {
        cin>>x;
        a[x].push_back(i);
        la[i]=x;
    }
    for(int i =1;i<=n;i++)
        cin>>s[i];
    int flag=0;
    ll sum=0;
    for(int i =1;i<=n;i++)
    {
        if(i==1) ans[i]=s[i];
        else
        {
            if(s[i]==-1)
            {
                s[i]=1e9+5;
                for(int j=0;j<a[i].size();j++)
                {
                   s[i]=min(s[a[i][j]],s[i]);
                }
                ans[i]=s[i]-s[la[i]];
                if(ans[i]<0) {flag=1;}
                if(a[i].size()==0 )ans[i]=0;
            }
            else
            {
                ans[i]=s[i]-s[la[i]];
                if(ans[i]<0) flag=1;
            }
        }
        sum+=ans[i];
        if(flag) break;
    }
    if(flag) cout<<-1<<endl;
    else
    cout<<sum<<endl;
    return 0;
}