题解 | #我是谁？#

#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<pair<int,int>>g[200005];
int dp[200005];
int chu[200005];
int qian[200005];
int dpp[200005];
int cun[200005];

void dfs(int a,vector<int>&h){
    for(auto [zhi,zi]:g[a]){
        dfs(zi,h);
        dp[a]+=dp[zi];
    }
    dp[a]+=h[a];
    return;
}
void dfs2(int a,int fu,vector<int>&h){
    for(int i=0;i<g[a].size();i++){
     if(i==0){
         dpp[a]+=(g[a][i].first);
     }else{
        dpp[a]+=(g[a][i].first-g[a][i-1].first); 
     }
        dpp[g[a][i].second]+=dpp[a];
        cun[g[a][i].second]=dpp[g[a][i].second];
        dfs2(g[a][i].second,a,h);
        dpp[a]+=dp[g[a][i].second];
    }
    return;
}
signed main(){
    int n;
    cin>>n;
    vector<int>h(n+1,0);
    for(int i=1;i<=n;i++){
        cin>>h[i];
    }
    vector<int>f(n+1,0);
    vector<int>w(n+1,0);
    for(int i=2;i<=n;i++){
        cin>>f[i];
    
    }
     for(int i=2;i<=n;i++){
        cin>>w[i];
    }
    for(int i=2;i<=n;i++){
        g[f[i]].push_back({w[i],i});
    }
    for(int i=1;i<=n;i++){
        sort(g[i].begin(),g[i].end());
    }
    dfs(1,h);
      dfs2(1,1,h);
    for(int i=1;i<=n;i++){
        cout<<cun[i]+dp[i]<<' ';
    }
}

关于这个题，看到说了后缀，其实这个题我不同的是我还用了后缀，其实我感觉这题更考察的是对dfs理解，让我先来解释一下我的数组含义，cun的意思是当水流刚好达到该点，且一滴水都没有流到该点时，需要用的量，而dp的意思则反过来，dp的意思是，以该点为根节点的子树里，当该子树被彻底灌满的时候，所需要的水量，很显然两者相加就是每个点的答案，一开始我们根据题意需要把每个w排序，按照从低到高排序，对于兄弟节点之间，每次dpp要上升的量都是两兄弟节点所接高度的差，但是我为什么没用dpp来代替cun呢，因为dpp同样还要有一个作用那就是接受子节点的水量反馈，所以cun在dpp接受了父节点(即dpp[a])的时候就即时保存即可。  祝你ac~思密达