#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pi pair<int, int>
#define pl pair<ll, ll>
#define f first
#define s second
#define vi vector<int>
#define vl vector<ll>
#define vvi vector<vi>
#define vvl vector<vl>
#define vpl vector<pl>
#define vpi vector<pi>
#define sz(x) x.size()
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define F0R(i,a) FOR(i,0,(a))
#define ROF(i,a,b) for(ll i=(b)-1;i>=(a);i--)
#define R0F(i,a) ROF(i,0,(a))
#define trav(el, v) for(auto &el : v)
#define nl endl
#define end(v) v.end()
#define bg(v) v.begin()
#define pb push_back
#define all(v) bg(v),end(v)
#define sor(v) sort(all(v))


vl w, p;
vvi g;
vector<array<ll, 4>> mx;
vl f;
ll sol;

void dfs(int u){
    trav(v, g[u]){
        dfs(v);
        ll cur = mx[v][0] + w[v];
        if(cur > mx[u][0]){
            f[u] = v;
            mx[u][2] = mx[u][1];
            mx[u][1] = mx[u][0];
            mx[u][0] = cur;
        }
        else if(cur > mx[u][1]){
            mx[u][2] = mx[u][1];
            mx[u][1] = cur;
        }
        else if(cur > mx[u][2]){
            mx[u][2] = cur;
        }
    }
}

void dfs2(int u){
    sol = max(sol, mx[u][0] + mx[u][1] + max(mx[u][2], mx[u][3]));
    trav(v, g[u]){
        mx[v][3] = max((f[u] == v ? mx[u][1] : mx[u][0]), mx[u][3]) + w[v];
        dfs2(v);
    }
}

void Bumerang(int n, int q, int* P, int* W, int* s, int* k, long long* ans){
    w.resize(n + 1);
    p.resize(n + 1);
    FOR(i, 2, n + 1){
        w[i] = W[i];
        p[i] = P[i];
    }
    if(n * q <= 100000000){
        g.resize(n + 1);
        FOR(i, 2, n + 1){
            g[p[i]].pb(i);
        }
        FOR(i, 1, q + 1){
            sol = 0;
            f.clear();
            mx.clear();
            mx.resize(n + 1, {0, 0, 0, 0});
            f.resize(n + 1);
            w[s[i]] = k[i];
            dfs(1);
            dfs2(1);
            ans[i] = sol;
            /*FOR(j, 1, n + 1){
                cerr << j << ": ";
                F0R(k, 4)cerr << mx[j][k] << " ";
                cerr << nl;
            }
            cerr << nl;*/
        }
    }
    else{
        g.resize(n + 1);
        FOR(i, 2, n + 1){
            g[p[i]].pb(i);
            g[i].pb(p[i]);
        }
        int c;
        FOR(i, 1, n + 1){
            if(sz(g[c]) == n - 1){
                c = i;
                break;
            }
        }
        multiset<ll> st;
        FOR(i, 2, n + 1) st.insert(w[i]);
        FOR(i, 1, q + 1){
            st.erase(st.find(w[s[i]]));
            w[s[i]] = k[i];
            st.insert(w[s[i]]);
            auto it = --end(st);
            ll sol = 0;
            F0R(j, 3){
                sol += (*it);
                it--;
            }
            ans[i] = sol;
        }
    }
}






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

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

*/