顺丰笔试8.31 第二题 圣诞树 AC

#include<iostream>
#include<vector>

using namespace std;

vector<vector<long long>> children;
vector<long long> value;

void dfs(int u,long long &pos,long long &neg){
    for(int v:children[u]){
        long long tp=0,tn=0;
        dfs(v,tp,tn);
        pos = max(pos,tp);
        neg = max(neg,tn);
    }
    long long val = value[u]+pos-neg;
    if(val>0){
        neg+=val;
    }
    else{
        pos-=val;
    }
    pos=pos;
    neg=neg;
}

int main(){
    int n;
    cin>>n;
    children.resize(n+1);
    value.resize(n+1);
    for(int i=2;i<=n;++i){
        int p;
        cin>>p;
        children[p].push_back(i);
    }
    for(int i=1;i<=n;++i){
        cin>>value[i];
    }
    long long pos=0,neg=0;
    dfs(1,pos,neg);
    cout<<pos+neg<<endl;
    return 0;
}