#include <bits/stdc++.h>
using namespace std;
using ll=long long;

#define pb push_back
#pragma GCC optimize("O3")
#define N 200050
vector<array<ll,2>>g[N];
ll mx[N],gr[N];

void dfs1(ll u){
    mx[u]=0;
    for(auto[v,w]:g[u]){
        dfs1(v);
        mx[u]=max(mx[u],mx[v]+w);
    }
}

void dfs2(ll u,ll cur){
    multiset<ll>lk;
    for(auto[v,w]:g[u]){
        lk.insert(mx[v]+w);
    }
    gr[u]=cur;
    for(auto[v,w]:g[u]){
        lk.erase(lk.find(mx[v]+w));
        if(lk.empty())dfs2(v,cur+w);
        else{
            cur=max(cur,*prev(lk.end()));
            dfs2(v,cur+w);
        }
    }
}

void Bumerang(int n, int q, int* p, int* w, int* s, int* k, long long* ans){
    //za svaki centroid drzim najduze pathove koji krecu iz njega?
    //jebiga nemam vremena za centroidnu

    for(int i=1;i<=q;++i){
        w[s[i]]=k[i];
        for(int i=1;i<=n;++i)
            g[i].clear();
        for(int i=2;i<=n;++i)
            g[p[i]].pb({i,w[i]});
        dfs1(1);
        dfs2(1,0);
        ll Ans=0;
        for(int u=1;u<=n;++u){
            vector<ll>tp;
            for(auto[v,w]:g[u]){
                tp.pb(mx[v]+w);
            }
            sort(tp.rbegin(),tp.rend());
            if(tp.size()>=3)Ans=max(Ans,tp[0]+tp[1]+tp[2]);
            if(tp.size()>=2){
                Ans=max(Ans,tp[0]+tp[1]+gr[u]);
            }
        }
        ans[i]=Ans;
    }

    return;
}

#undef N