#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
#define mp make_pair
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx")
template<typename T1,typename T2>void chmn(T1 &x,const T2 &y){x=x<y?x:y;}
template<typename T1,typename T2>void chmx(T1 &x,const T2 &y){x=x>y?x:y;}
const int N=2e5+50;
const ll INF=1e18;
vector<int>E[N];
int par[N],val[N],n;
ll dp[N],dp1[N];
void DFSS(int u){
    for(auto i:E[u]){
        DFSS(i);
        chmx(dp[u],dp[i]+val[i]);
    }
}
void DFSS1(int u){
    int m=E[u].size();
    ll prefmx[m+1]={0},sufmx[m+1]={0};
    for(int i=0;i<m;i++)prefmx[i+1]=max(prefmx[i],dp[E[u][i]]+val[E[u][i]]);
    for(int i=m-1;i>=0;i--)sufmx[i]=max(sufmx[i+1],dp[E[u][i]]+val[E[u][i]]);
    for(int i=0;i<m;i++){
        dp1[E[u][i]]=max({dp1[u],prefmx[i],sufmx[i+1]})+val[E[u][i]];
    }
    for(auto i:E[u])DFSS1(i);
}

int sajz[N];
void DFSsetup(int u){
    sajz[u]=1;
    for(auto i:E[u])DFSsetup(i),sajz[u]+=sajz[i];
    int mxsz=0;
    for(auto i:E[u])chmx(mxsz,sajz[i]);
    for(auto &i:E[u])if(sajz[i]==mxsz){swap(i,E[u][0]);break;}
}
int head[N],tail[N],in[N],tajm;
multiset<ll>Set[N];
void HLD(int u){
    in[u]=++tajm;
    if(head[u]==0)head[u]=u;
    if(!E[u].empty())head[E[u][0]]=head[u];
    for(auto i:E[u])HLD(i);
    if(E[u].empty())tail[u]=u;
    else tail[u]=tail[E[u][0]];
    for(int i=1;i<E[u].size();i++)Set[u].insert(0);
}
struct SegTree{
    int root,nc,lc[2*N],rc[2*N];ll maks[2*N],lazy[2*N];
    void update(int &c,ll x){
        if(!c)c=++nc;
        maks[c]+=x;
        lazy[c]+=x;
    }
    void push(int &c){
        if(!c)c=++nc;
        update(lc[c],lazy[c]);
        update(rc[c],lazy[c]);
        lazy[c]=0;
    }
    void Update(int &c,int ss,int se,int qs,int qe,ll x){
        if(!c)c=++nc;
        if(qs>qe||qe<ss||se<qs)return;
        if(qs<=ss&&se<=qe){update(c,x);return;}
        int mid=ss+se>>1;push(c);
        Update(lc[c],ss,mid,qs,qe,x);
        Update(rc[c],mid+1,se,qs,qe,x);
        maks[c]=max(maks[lc[c]],maks[rc[c]]);
    }
    ll Get(int &c,int ss,int se,int qs,int qe){
        if(!c)c=++nc;
        if(qs>qe||qe<ss||se<qs)return 0;
        if(qs<=ss&&se<=qe)return maks[c];
        int mid=ss+se>>1;push(c);
        return max(Get(lc[c],ss,mid,qs,qe),Get(rc[c],mid+1,se,qs,qe));
    }
}ST,ST1;

ll Getf(int u){
    int h=head[u],t=tail[u];
    ll x=ST.Get(ST.root,1,n,in[u],in[t]);
    if(u!=h)x-=ST1.Get(ST1.root,1,n,in[h],in[par[u]]);
    return x;
}
void Update(int u,ll w){
    //printf("*%i %i\n",u,w);
    int h=head[u],t=tail[u];
    ll vrednost=Getf(h);
    ST.Update(ST.root,1,n,in[u],in[t],w-val[u]);
    ST1.Update(ST1.root,1,n,in[u],in[u],w-val[u]);
    val[u]=w;
    while(head[u]!=1){
        //printf(" %i\n",u);
        u=head[u];
        int p=par[u];
        //printf("%i\n",p);
        ll Flast=*Set[p].rbegin();
        //printf("DA\n");
        Set[p].erase(Set[p].find(vrednost));
        //printf("da\n");
        Set[p].insert(Getf(u));
        //printf("da\n");
        ll Fnew=*Set[p].rbegin();
        vrednost=Getf(head[p]);
        ST.Update(ST.root,1,n,in[p],in[p],Fnew-Flast);
        u=p;
    }
}
void Bumerang(int n1,int q,int* p,int* w,int* U,int* W,ll* ans){
    n=n1;
    for(int i=2;i<=n;i++){
        par[i]=p[i];
        val[i]=w[i];
        E[par[i]].pb(i);
    }

    int deg[n+10]={0};
    for(int i=2;i<=n;i++)deg[i]++,deg[par[i]]++;
    bool subtask2=false;
    int cnt2=0;
    for(int i=1;i<=n;i++)if(deg[i]>1)cnt2++;
    if(cnt2==1)subtask2=true;
    bool subtaskbrute=false;
    if((n<=5000&&q<=5000)||q==1)subtaskbrute=true;
    //for(int i=1;i<=n;i++){printf("%i: ",i);for(auto j:E[i])printf("%i ",j);printf("\n");}
    //for(int i=1;i<=n;i++)printf("%i ",val[i]);printf("\n");
    if(subtask2){
        multiset<ll>st;
        for(int i=2;i<=n;i++)st.insert(val[i]);
        for(int I=1;I<=q;I++){
            st.erase(st.find(val[U[I]]));
            val[U[I]]=W[I];
            st.insert(W[I]);
            ll x=*st.rbegin();
            st.erase(st.find(x));
            ll y=*st.rbegin();
            st.erase(st.find(y));
            ll z=*st.rbegin();
            st.erase(st.find(z));
            ans[I]=x+y+z;
            st.insert(x);
            st.insert(y);
            st.insert(z);
        }
        return;
    }
    if(subtaskbrute){
        for(int I=1;I<=q;I++){
            val[U[I]]=W[I];
            for(int i=1;i<=n;i++)dp[i]=dp1[i]=0;
            DFSS(1);
            DFSS1(1);
            ll res=0;
            for(int u=1;u<=n;u++){
                vector<ll>vals;
                if(u!=1)vals.pb(dp1[u]);
                for(auto i:E[u])vals.pb(dp[i]+val[i]);
                if(vals.size()<3)continue;
                ll ind1=-1,ind2=-1,ind3=-1;
                for(int i=0;i<vals.size();i++)if(ind1==-1||vals[ind1]<=vals[i])ind1=i;
                for(int i=0;i<vals.size();i++)if(i!=ind1&&(ind2==-1||vals[ind2]<vals[i]))ind2=i;
                for(int i=0;i<vals.size();i++)if(i!=ind1&&i!=ind2&&(ind3==-1||vals[ind3]<vals[i]))ind3=i;
                chmx(res,vals[ind1]+vals[ind2]+vals[ind3]);
            }
            ans[I]=res;
        }
        return;
    }

    DFSsetup(1);
    HLD(1);
    //for(int i=1;i<=n;i++)printf("%i: %i %i %i\n",i,in[i],head[i],tail[i]);
    for(int i=1;i<=n;i++)val[i]=0;
    for(int i=2;i<=n;i++)Update(i,w[i]);
    for(int I=1;I<=q;I++){
        Update(U[I],W[I]);
        int v=E[1][0];
        ll x=Getf(v);
        Set[1].insert(x);
        ll X=*Set[1].rbegin();
        Set[1].erase(Set[1].find(X));
        ll Y=*Set[1].rbegin();
        Set[1].erase(Set[1].find(Y));
        ll Z=*Set[1].rbegin();
        Set[1].erase(Set[1].find(Z));
        ans[I]=X+Y+Z;
        Set[1].insert(X);
        Set[1].insert(Y);
        Set[1].insert(Z);
        Set[1].erase(Set[1].find(x));
    }
}