#include <bits/stdc++.h>
#define pii pair<ll,ll>
#define fi first
#define se second
#define MAXN (int)2e5+5
using namespace std;
typedef long long ll;
vector<pii>g[MAXN];
ll dp[MAXN];
void dfs(int x,int p){
    dp[x]=0;
    for(pii&z:g[x]){
        if(z.fi^p){
            dfs(z.fi,x);
            dp[x]=max(dp[x],dp[z.fi]+z.se);
        }
    }
}
ll dfs2(int x,int p){
    ll e=0;
    multiset<pii>s,s2;
    pii mx1={0,0},mx2={0,0},mx3={-1,0};
    for(pii&z:g[x]){
        if(mx1.fi<dp[z.fi]+z.se){
            mx3=mx2;
            mx2=mx1;
            mx1={dp[z.fi]+z.se,z.fi};
        }else if(mx2.fi<dp[z.fi]+z.se){
            mx3=mx2;
            mx2={dp[z.fi]+z.se,z.fi};
        }else{
            mx3={dp[z.fi]+z.se,z.fi};
        }
    }if(mx3.fi!=-1){
        e=mx1.fi+mx2.fi+mx3.fi;
    }
    for(pii&z:g[x]){
        if(z.fi==p){continue;}
        ll r=(z.fi==mx1.se?mx2.fi:mx1.fi);
        ll o=dp[x];
        dp[x]=r;
        e=max(e,dfs2(z.fi,x));
        dp[x]=o;
    }
    return e;
}
void Bumerang(int n, int q, int* p, int* w, int* s, int* k, ll* ans){
    if(n>5000){
        set<array<int,3>>ss;
        map<pii,int>m;
        for(int i=2;i<=n;i++){
                g[i].emplace_back(p[i],w[i]);
                g[p[i]].emplace_back(i,w[i]);
                ss.insert({-w[i],i,p[i]});
                m[{i,p[i]}]=w[i];

        }
        for(int i=1;i<=q;i++){
            int a=s[i],b=k[i];
            ll z=0;
            ss.erase({-m[{a,p[a]}],a,p[a]});
            ss.insert({-b,a,p[a]});
            m[{a,p[a]}]=b;
            set<array<int,3>>s2;
            for(int j=0;j<3;j++){
                array<int,3>x=*ss.begin();ss.erase(ss.begin());
                s2.insert(x);
                x[0]=-x[0];
                z+=x[0];
            }while(!s2.empty()){
                array<int,3> x=*s2.begin();
                ss.insert(x);
                s2.erase(s2.begin());
            }
            ans[i]=z;
        }
        return;
    }
    for(int i=2;i<=n;i++){
            g[p[i]].emplace_back(i,w[i]);
            g[i].emplace_back(p[i],w[i]);
    }
    for(int i=1;i<=q;i++){
        int a=s[i],b=k[i];
        for(pii&x:g[p[a]]){
            if(x.fi==a){
                x.se=b;break;
            }
        }for(pii&x:g[a]){
            if(x.fi==p[a]){
                x.se=b;break;
            }
        }
        dfs(1,0);
        ans[i]=dfs2(1,0);
    }
}