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

map<pair<int,int>,long long>grane;
vector<vector<int>>graf;

long long dfs(int nod,int prnt){
    //cerr<<"usao u "<<nod<<" iz "<<prnt<<endl;
    if(graf[nod].size()==1){
        //cerr<<nod<<" -> "<<prnt<<", vracam "<<0<<" + "<<grane[{nod,prnt}]<<'\n';
        return grane[{nod,prnt}];
    }
    long long grn=0;
    for(auto i:graf[nod]){
        if(i==prnt)continue;
        grn=max(grn,dfs(i,nod));
    }
    //cerr<<nod<<" -> "<<prnt<<", vracam "<<grn<<" + "<<grane[{nod,prnt}]<<'\n';
    return grn+grane[{nod,prnt}];
}

void Bumerang(int n, int q, int* p, int* w, int* s, int* k, long long* ans){
    graf.resize(n+1);
    for(int i=2;i<=n;i++){
        grane[{i,p[i]}]=w[i];
        grane[{p[i],i}]=w[i];
        graf[p[i]].push_back(i);
        graf[i].push_back(p[i]);
    }
    vector<int>boom;
    for(int i=1;i<=n;i++){
        if(graf[i].size()>=3)boom.push_back(i);
    }
    if(n<=200 && q<=200){
        //testcase 1 bruteforce
        for(int i=1;i<=q;i++){
            long long res=0;
            //cerr<<"TESTACE "<<i<<"____________________________________"<<'\n';
            int cvor=s[i];
            int par=p[cvor];
            long long tezina=k[i];
            //cerr<<"Menjamo "<<cvor<<' '<<par<<" u "<<tezina<<'\n';
            grane[{cvor,par}]=tezina;
            grane[{par,cvor}]=tezina;
            for(auto root:boom){
                long long put1=0,put2=0,put3=0;
                for(auto dete:graf[root]){
                    long long put=dfs(dete,root);
                    //cerr<<"Vratio se u loop vratio "<<put<<'\n';
                    if(put1<=put){
                        put3=put2;
                        put2=put1;
                        put1=put;
                    }
                    else if(put2<=put){
                        put3=put2;
                        put2=put;
                    }
                    else if(put3<=put)put3=put;
                }
                //cerr<<"Za cvor "<<root<<" najjaci putevi su "<<put1<<' '<<put2<<' '<<put3<<'\n';
                res=max(res,put1+put2+put3);
            }
            ans[i]=res;
        }
    }
    else if(boom.size()==1){
        multiset<long long>ms;
        for(int i=1;i<=n;i++)ms.insert(w[i]);
        for(int i=1;i<=q;i++){
            ms.erase(ms.find(w[s[i]]));
            w[s[i]]=k[i];
            ms.insert(w[s[i]]);
            ans[i]=*prev(ms.end())+*prev(prev(ms.end()))+*prev(prev(prev(ms.end())));
        }
    }
    else{
        //radi testcase gde je root uvek optimalni boomerang
        return;
    }
}