UJGOI 2022 D. Anton the guard

#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")

constexpr int N = (int)1e6+11;
constexpr long long INF = (long long)1e18;

vector<pair<int,int>> initialGraph[N];
long long w[N];
vector<int> g[N],compressedGraph[N];
int deep[N];
pair<long long,int> mn[N][2];
int p[N];
long long dp[N];

void dfs_down_edges(int v,int pr = -1){
    for(auto&[to,len] : initialGraph[v]){
        if(to == pr) continue;
        p[to] = v;
        w[to] = w[v] + len;
        g[v].push_back(to);
        deep[to] = deep[v] + 1;
        dfs_down_edges(to,v);
    }
    return;
}

int dfs_compress(int v,int depth,long long& total_weight){
    if(deep[v] == depth){
        return v;
    }
    compressedGraph[v].clear();
    mn[v][0] = mn[v][1] = make_pair(INF,-1);
    for(auto& to : g[v]){
        int u = dfs_compress(to,depth,total_weight);
        if(u != -1){
            compressedGraph[v].push_back(u);
            if(deep[u] == depth){
                long long len = w[p[u]] - w[v];
                mn[v][1] = min(mn[v][1],make_pair(dp[p[u]]-len,u));
            } else {
                long long len = w[u] - w[v];
                mn[v][1] = min(mn[v][1],make_pair(mn[u][0].first-len,u));
            }
            if(mn[v][0] > mn[v][1]) swap(mn[v][0],mn[v][1]);
        }
    }
    swap(g[v],compressedGraph[v]);
    if(g[v].size() > 1){
        for(auto& to : g[v]){
            total_weight += w[to] - w[v]; /// add the length of the edges
        }
        return v;
    }
    else
        return (g[v].empty() ? -1 : g[v][0]);
}

void dfs_recalc_dp(int v,int depth,long long min_len,const long long& total_weight){
    if(deep[v] == depth){
        int len = w[v] - w[p[v]];
        min_len = min(min_len,dp[p[v]]-len);
        dp[v] = 2 * total_weight + min_len;
        return;
    }
    for(auto& to : g[v]){
        long long len = w[to] - w[v];
        long long next_min_len = min_len - len;
        bool goMinVertex = (mn[v][0].second == to);
        next_min_len = min(next_min_len,mn[v][goMinVertex].first-len);
        dfs_recalc_dp(to,depth,next_min_len,total_weight);
    }
    return;
}

signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

    int n;
    cin >> n;

    for(int i = 2; i <= n; i++){
        cin >> p[i];
    }

    for(int i = 2; i <= n; i++){
        cin >> w[i];
    }

    for(int i = 2; i <= n; i++){
        initialGraph[p[i]].push_back(make_pair(i,w[i]));
        initialGraph[i].push_back(make_pair(p[i],w[i]));
    }

    int root = 1;

    deep[root] = 1;
    dfs_down_edges(root);
    int max_depth = 1;

    for(int depth = 2; depth <= n; depth++){
        long long total_weight = 0;
        root = dfs_compress(root,depth,total_weight);
        if(root == -1) break;
        if(deep[root] == depth){
            total_weight = w[root] - w[p[root]];
        }
        max_depth = depth;
        dfs_recalc_dp(root,depth,INF,total_weight);
    }

    long long ans = INF;
    for(int i = 1; i <= n; i++){
        if(deep[i] == max_depth)
            ans = min(ans,dp[i]);
    }

    cout << ans << "\n";

    return 0;
}