#include #include #include using namespace std; using ll = long long; using ull = unsigned long long; int RQop(int l,int r){ return max(l,r); } int RQe(){ return -1; } using RQ = atcoder::segtree; int N; vector> E; vector A; vector B; RQ G; vector dp; int dfs(int p,int i=0){ int pre_i = i; for(int e : E[p]) i = dfs(e,i) + 1; G.set(A[p],i); dp[A[p]] = B[p]; ll b = B[p]; while(true){ int nx = G.min_left(A[p],[pre_i](int j){ return pre_i > j; }) - 1; if(nx == -1) break; if(dp[nx] > b){ dp[nx] -= b; break; } b -= dp[nx]; dp[nx] = 0; G.set(nx,-1); } return i; } int main(){ cin >> N; E.resize(N); for(int i=1; i> p; p--; E[p].push_back(i); } A.resize(N); for(int i=0; i> A[i]; A[i]--; } B.resize(N); for(int i=0; i> B[i]; dp.assign(N,0); G = RQ(N); dfs(0); ll ans = 0; for(int i=0; i