#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;
    for(pii&z:g[x]){
        s.insert({-dp[z.fi]-z.se,z.fi});
    }int og=s.size();
    for(int j=0;j<3&&og>=3;j++){
        pii xx=*s.begin();s.erase(s.begin());
        s2.insert(xx);
        xx.fi=-xx.fi;
        e+=xx.fi;
    }while(!s2.empty()){
        pii xx=*s2.begin();
        s.insert(xx);
        s2.erase(s2.begin());
    }
    for(pii&z:g[x]){
        if(z.fi==p){continue;}
        int xx=(*s.begin()).se;
        if(xx==z.fi){
            s.erase(s.begin());
        }
        int r=-(*s.begin()).fi;
        if(xx==z.fi){
            s.insert({dp[z.fi]-z.se,z.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(min(n,q)>6000){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);
    }
}