#include <bits/stdc++.h>

using namespace std;

#define MAXN 200001

int deg[MAXN];
vector<pair<int,int>> adj[MAXN];
long long dp[MAXN];

void dfs(int node,int pret)
{
    if ((int)adj[node].size()==1) return;
    for (pair<int,int> edge:adj[node])
    {
        int sled=edge.first,w=edge.second;
        if (sled==pret) continue;
        dfs(sled,node);dp[node]=max(dp[node],dp[sled]+w);
    }
}

long long newdp[3][MAXN];
long long kandidat=0;

void newdfs(int node,int pret)
{
    if ((int)adj[node].size()==1) return;
    for (pair<int,int> edge:adj[node])
    {
        int sled=edge.first,w=edge.second;
        if (sled==pret) continue;
        newdfs(sled,node);long long value=newdp[0][sled]+w;
        if (value>=newdp[0][node]) {newdp[2][node]=newdp[1][node];newdp[1][node]=newdp[0][node];newdp[0][node]=value;}
        else if (value>=newdp[1][node]) {newdp[2][node]=newdp[1][node];newdp[1][node]=value;}
        else if (value>newdp[2][node]) newdp[2][node]=value;
    }
}

void reroot(int node,int pret)
{
    if ((int)adj[node].size()>=3) kandidat=max(kandidat,newdp[0][node]+newdp[1][node]+newdp[2][node]);
    for (pair<int,int> edge:adj[node])
    {
        int sled=edge.first,w=edge.second;if (sled==pret) continue;
        pair<long long,pair<long long,long long>> pamtinode={newdp[0][node],{newdp[1][node],newdp[2][node]}};
        pair<long long,pair<long long,long long>> pamtisled={newdp[0][sled],{newdp[1][sled],newdp[2][sled]}};
        long long value=newdp[0][sled]+w;
        if (value==newdp[0][node]) {newdp[0][node]=newdp[1][node];newdp[1][node]=newdp[2][node];newdp[2][node]=0;}
        else if (value==newdp[1][node]) {newdp[1][node]=newdp[2][node];newdp[2][node]=0;}
        else if (value==newdp[2][node]) newdp[2][node]=0;
        if (newdp[0][node]+w>=newdp[0][sled]) {newdp[2][sled]=newdp[1][sled];newdp[1][sled]=newdp[0][sled];newdp[0][sled]=newdp[0][node]+w;}
        else if (newdp[0][node]+w>=newdp[1][sled]) {newdp[2][sled]=newdp[1][sled];newdp[1][sled]=newdp[0][node]+w;}
        else if (newdp[0][node]+w>newdp[2][sled]) newdp[2][sled]=newdp[0][node]+w;
        reroot(sled,node);
        newdp[0][node]=pamtinode.first;newdp[1][node]=pamtinode.second.first;newdp[2][node]=pamtinode.second.second;
        newdp[0][sled]=pamtisled.first;newdp[1][sled]=pamtisled.second.first;newdp[2][sled]=pamtisled.second.second;
    }
}

void Bumerang(int n, int q, int* p, int* w, int* s, int* k, long long* ans)
{
    for (int i=2;i<=n;i++) {deg[i]++;deg[p[i]]++;}
    bool subtask2=false;
    for (int node=1;node<=n;node++)
    {
        if (deg[node]==n-1) {subtask2=true;break;}
    }
    if (subtask2)
    {
        multiset<int> weights;for (int node=2;node<=n;node++) weights.insert(w[node]);
        for (int i=1;i<=q;i++)
        {
            weights.erase(weights.find(w[s[i]]));weights.insert(k[i]);w[s[i]]=k[i];
            auto it=weights.end();long long answer=0;
            it--;answer+=(*it);it--;answer+=(*it);it--;answer+=(*it);ans[i]=answer;
        }
        return;
    }
    if (n<=200 and q<=200)
    {
        for (int i=1;i<=q;i++)
        {
            w[s[i]]=k[i];for (int i=2;i<=n;i++) {adj[i].push_back({p[i],w[i]});adj[p[i]].push_back({i,w[i]});}
            long long answer=0;
            for (int node=1;node<=n;node++)
            {
                if ((int)adj[node].size()<3) continue;
                vector<long long> sumice;for (int node=1;node<=n;node++) dp[node]=0;
                for (pair<int,int> edge:adj[node]) {dfs(edge.first,node);sumice.push_back(dp[edge.first]+edge.second);}
                sort(sumice.begin(),sumice.end());reverse(sumice.begin(),sumice.end());
                answer=max(answer,sumice[0]+sumice[1]+sumice[2]);sumice.clear();
            }
            ans[i]=answer;for (int node=1;node<=n;node++) adj[node].clear();
        }
        return;
    }
    if (q==1)
    {
        /// 7 OK, 1 WA
        w[s[1]]=k[1];for (int i=2;i<=n;i++) {adj[i].push_back({p[i],w[i]});adj[p[i]].push_back({i,w[i]});}
        long long answer=0;for (int node=1;node<=n;node++) {newdp[0][node]=0;newdp[1][node]=0;newdp[2][node]=0;}
        newdfs(1,0);reroot(1,0);ans[1]=kandidat;return;
    }
};