#include <bits/stdc++.h>
#define pii pair<long long,long long>
#define fi first
#define sc second
#define pb push_back
#define all(x) (x).begin(), (x).end()

using namespace std;

const int MAXN = 2e5+5;

vector<vector<pii>> graf(MAXN);
vector<long long> mxrez(MAXN);
vector<long long> dist(MAXN);
long long trrez;
int nn ;


void dfs(int nod, int p, long long d)
{
    mxrez[nod] = d;
    dist[nod] = d;
    for(auto x: graf[nod])
    {
        if(x.fi==p)continue;
        dfs(x.fi,nod, d+x.sc);
        mxrez[nod] = max(mxrez[nod], mxrez[x.fi]);
    }
}

void solve(int nod, int p, int d)
{
    multiset<long long> setic;
    long long prez = 0;
    for(auto x: graf[nod])mxrez[x.fi]-=d;
    for(auto x: graf[nod])mxrez[nod]= max(mxrez[nod], mxrez[x.fi]);
    pii mx = {0,0};
    //for(int i=1; i<=nn; i++)cout << mxrez[i] << " ";cout << endl;
    if(graf[nod].size() >= 3)
    {
         for(auto x: graf[nod])
        {
            if(mx.fi > mxrez[x.fi])
            {
                mx.sc = mx.fi;
                mx.fi = mxrez[x.fi];
            }
            else if(mx.sc > mxrez[x.fi])mx.sc = mxrez[x.fi];
            setic.insert(mxrez[x.fi]);
            if(setic.size() > 3)setic.erase(setic.begin());
        }
        for(auto x: setic)prez+= x;
        trrez = max(trrez, prez);
    }
    for(auto x: graf[nod])
    {
        if(x.fi == p)continue;
        int prereznod = mxrez[nod];
        if(mxrez[x.fi] == mxrez[nod]) mxrez[nod] = mx.sc;
        mxrez[nod]+= x.sc;
        mxrez[x.fi] -=x.sc;
        solve(x.fi, nod, d+x.sc);
        mxrez[nod] = prereznod;
        mxrez[x.fi] +=x.sc;
    }
     for(auto x: graf[nod])mxrez[x.fi]+=d;
}


void Bumerang(int n, int q, int* p, int* w, int* s, int* k, long long* ans){

nn = n;
    for(int i=2; i<=n; i++)
    {
        graf[i].pb({p[i],w[i]});
        graf[p[i]].pb({i,w[i]});
    }
    if((n <= 5000 && q<=5000) || q == 1)
    {
        for(int i=1; i<=q; i++)
        {

            for(int j=1; j<=n; j++)graf[j].clear();
            w[s[i]] = k[i];
            for(int j=2; j<=n; j++)
            {
                graf[j].pb({p[j],w[j]});
                graf[p[j]].pb({j,w[j]});
            }
            dfs(1,1,0);
            //for(int i=1; i<=n; i++)cout << mxrez[i] << " ";cout << endl;
            trrez = 0;
            solve(1,1,0);
            ans[i] = trrez;
        }
    }
    else
    {

        int mxadj = 0;
        int node = -1;
        for(int i=1; i<=n; i++)
        {
            if((int)graf[i].size() > mxadj)
            {
                mxadj = (int)graf[i].size();
                node = i;
            }
        }
         if(mxadj == n-1)
        {
            multiset<long long> setic;
            for(auto x: graf[node])setic.insert(x.sc);
            //for(int i=2; i<=n; i++)setic.insert(w[i]);
            //for(auto x: setic)cout << x << endl;
            for(int j=1; j<=q; j++)
            {
                long long x = w[s[j]];
                setic.erase(setic.find(w[s[j]]));
                w[s[j]] = k[j];
                //cout << k[j] << endl;
                setic.insert(k[j]);
                //for(auto x: setic)cout << x << endl;
                long long sum = *prev(setic.end()) + *prev(prev(setic.end())) + *prev(prev(prev(setic.end())));
                ans[j] = sum;
            }
        }
    }
}

/*
7 10
0 3 1 3 3 3 3
0 1 2 3 4 5 6
2 3 2 5 3 2 3 2 7 6
4 3 6 1 5 4 3 6 1 5
*/

/*
6 3
0 1 1 1 2 2
0 3 4 5 2 1
5 4 2
10 1 8
*/