#include <bits/stdc++.h>

#define fi first
#define se second
#define pll pair<ll,ll>

using namespace std;

using ll = long long;

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

    ll i,ff,tren;
    vector<vector<pll>>adj(n);
    vector<ll>cnt(n),dp(n);
    for(i=2;i<=n;i++)
    {
        adj[p[i]-1].push_back({w[i],i-1});
        adj[i-1].push_back({w[i],p[i]-1});
    }
    if(n*q>=1e8)
    {
        return;
    }
    for(ff=1;ff<=q;ff++)
    {
        ans[ff]=0;
         //        cout << "lala" << endl;
        w[s[ff]]=k[ff];
        for(auto &x:cnt)
        {
            x=0;
        }

         queue<ll>qee;
         for(auto &x:dp)
         {
             x=0;
         }
         for(i=1;i<n;i++)
         {
             if(adj[i].size()==1)
             {
                 qee.push(i);
                 dp[i]=0;
             }
         }
      //   cout << "lala" << endl;
         while(!qee.empty())
         {
             tren=qee.front();
             qee.pop();
             for(auto &x:adj[tren])
             {
                 if(x.se!=p[tren+1]-1)
                 {
                     dp[tren]=max(dp[x.se]+w[x.se+1],dp[tren]);
                 }
             }
             if(tren==0)
             {
                 continue;
             }
             cnt[p[tren+1]-1]++;
             if(cnt[p[tren+1]]==adj[p[tren+1]].size()-1)
             {
                 qee.push(p[tren+1]-1);
             }

         }
             queue<pll>qu;
             ll wejt,mx;
      //   cout << "lala" << endl;
         qu.push({0ll,0ll});


         while(!qu.empty())
         {
             auto lala=qu.front();
             tren=lala.fi;
             wejt=lala.se;
             qu.pop();
             ll cntr=0,check=-1;
             mx=0;
             ll mx1=0,mx2=0,mx3=0;
             for(auto &x:adj[tren])
             {
                 if(x.se==p[tren+1]-1)
                 {
                     continue;
                 }
                 cntr++;
                 if(dp[x.se]+w[x.se+1]>=mx)
                 {

                     mx=dp[x.se]+w[x.se+1];
                     check=x.se;
                 }
                 if(dp[x.se]+w[x.se+1]>=mx1)
                 {
                     mx3=mx2;
                     mx2=mx1;
                     mx1=dp[x.se]+w[x.se+1];
                 }
                 else if(dp[x.se]+w[x.se+1]>=mx2)
                 {
                     mx3=mx2;
                     mx2=dp[x.se]+w[x.se+1];
                 }
                 else if(dp[x.se]+w[x.se+1]>=mx3)
                 {
                     mx3=dp[x.se]+w[x.se+1];
                 }

             }

             if(cntr>=2)
             {
                 ans[ff]=max(ans[ff],mx1+mx2+wejt);
             }
             if(cntr>=3)
             {
                 ans[ff]=max(ans[ff],mx1+mx2+mx3);
             }
             for(auto &x:adj[tren])
             {
                 if(x.se==p[tren+1]-1)
                 {
                     continue;
                 }
                 if(x.se==check)
                 {
                     qu.push({x.se,w[x.se+1]+max(wejt,mx2)});
                 }
                 else
                 {
                     qu.push({x.se,w[x.se+1]+max(wejt,mx)});
                 }
             }

         }
      //   cout << mx1 << " " << mx2 << " " << mx3 << endl;

    }




}