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

const int MAXN=200009;
vector<pair<int,int>> graf[MAXN];
pair<int,int> pokriva_listove[MAXN];
int indx=1;
void dfs(int node,int par){
    pokriva_listove[node].first=indx;
    for(auto x:graf[node]){
        if(x.first==par) continue;
        dfs(x.first,node);
    }
    if(graf[node].size()==1&&node!=1)
        ++indx;
    pokriva_listove[node].second=indx;

}
struct Cvor{
    long long val=0,lazy=0;
};
Cvor seg[4*MAXN];
void push(int node,int l,int d){
    seg[node].val+=seg[node].lazy;
    if(l!=d){
        seg[2*node].lazy+=seg[node].lazy;
        seg[2*node+1].lazy+=seg[node].lazy;
    }
    seg[node].lazy=0;
}

void upd(int node,int l,int d,int poc,int kr,long long val){
    push(node,l,d);
    if(poc<=l&&d<=kr){
        seg[node].lazy+=val;
        push(node,l,d);
        return;
    }
    if(d<poc||kr<l) return;
    int s=l+d>>1;
    upd(2*node,l,s,poc,kr,val);upd(2*node+1,s+1,d,poc,kr,val);
    seg[node].val=max(seg[2*node].val,seg[2*node+1].val);
}
pair<int,long long> postavi0(int node,int l,int d){
    push(node,l,d);
    if(l==d){
        long long a=seg[node].val;
        seg[node].val=0;
        return {l,a};
    }
    int s=l+d>>1;
    push(2*node,l,s);push(2*node+1,s+1,d);
    pair<int,long long> rez;
    if(seg[2*node].val>=seg[2*node+1].val)
        rez=postavi0(2*node,l,s);
    else
        rez=postavi0(2*node+1,s+1,d);
    seg[node].val=max(seg[2*node].val,seg[2*node+1].val);
    return rez;
}
void postavi(int node,int l,int d,int ind,long long x){
    push(node,l,d);
    if(l==d){
        seg[node].val=x;
        return;
    }
    int s=l+d>>1;
    if(ind<=s)
        postavi(2*node,l,s,ind,x);
    else
        postavi(2*node+1,s+1,d,ind,x);
    seg[node].val=max(seg[2*node].val,seg[2*node+1].val);
}

void dfs2(int node,int par,long long val){
    for(auto x:graf[node]){
        if(x.first==par) continue;
        dfs2(x.first,node,val+x.second);
    }
    if(graf[node].size()==1&&node!=1)
        upd(1,1,indx,pokriva_listove[node].first,pokriva_listove[node].first,val);

}








void Bumerang(int n, int q, int* p, int* w, int* s, int* k, long long* ans){
    for(int i=2; i<=n; i++){
        graf[i].push_back({p[i],w[i]});
        graf[p[i]].push_back({i,w[i]});
    }
    dfs(1,0);
    dfs2(1,0,0);
    for(int i=1; i<=q; i++){
        upd(1,1,indx,pokriva_listove[s[i]].first,pokriva_listove[s[i]].second-1,k[i]-w[s[i]]);
        w[s[i]]=k[i];
        pair<int,long long> m1=postavi0(1,1,indx);
        pair<int,long long> m2=postavi0(1,1,indx);
        pair<int,long long> m3=postavi0(1,1,indx);
        ans[i]=m1.second+m2.second+m3.second;
        postavi(1,1,indx,m1.first,m1.second);
        postavi(1,1,indx,m2.first,m2.second);
        postavi(1,1,indx,m3.first,m3.second);
    }




    return;
}
/*
10 3
0 1 1 1 1 3 3 6 6 6
0 1 1 1 1 1 1 1 1 1
6 5 2
2 10 15
*/