出现了插排插插排经典题目！

思路

我们可以将众多插排抽象成一个有向无环图。如果有环的话会造成短路，所以不可能存在环。

这道题最先想到的是dfs每个点求出答案，但这样复杂度很高，会超时。所以我们需要记忆化，每求出一个点的答案就将它保存下来，如果下次再遍历到这个点就能直接得出答案，无需再求一遍。

AC Code

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e6+5;
ll n,ans[N];
struct node{
    ll val;
    vector<ll> son;
}a[N];
ll dfs(ll x){
    if(ans[x])
        return ans[x];
    ans[x]=a[x].val;
    for(auto i=a[x].son.begin();i!=a[x].son.end();i++)
        ans[x]+=dfs(*i);
    return ans[x];   
}
int main(){
    scanf("%lld",&n);
    for(ll i=2,x;i<=n;i++)
        scanf("%lld",&x),a[x].son.push_back(i);
    for(ll i=1;i<=n;i++)
        scanf("%lld",&a[i].val);
    for(ll i=1;i<=n;i++)
        printf("%lld ",dfs(i));
    return 0;
}