#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);
long long trrez;

void dfs(int nod, int p, long long d)
{
    mxrez[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]);
        //mxrez[x.fi] = x.sc;
    }
    if(nod == p)
    {
        vector<long long> po;
        for(auto x: graf[nod])po.pb(mxrez[x.fi]);
        sort(all(po));
        reverse(all(po));
        //for(auto x: po)cout << x << endl;
        //cout << endl;
        trrez = 0;
        for(int i =0; i<3; i++)trrez+=po[i];
    }
    //mxrez[nod] = d;
}


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].pb({p[i],w[i]});
        graf[p[i]].pb({i,w[i]});
    }
    if(n <= 200 && q<=200)
    {
        for(int i=1; i<=q; i++)
        {
            graf = vector<vector<pii>>(n+5);
            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]});
            }

            long long mx = 0;
            for(int j=1; j<=n; j++)
            {
                if(graf[j].size() < 3)continue;
                dfs(j,j,0);
                mx = max(mx,trrez);
                for(int k=1; k<=n; k++)mxrez[k] = 0;
            }
            ans[i] = mx;
        }
    }
    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 1000000000 1000000000 1000000000 1000000000 1000000000
5 4 2
10 1 8
*/