#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC target("avx2")

using namespace std;
using ll = long long;
#define pb push_back

const int N = 2e5+5;
set<array<ll, 2>> g[N];
vector<array<ll, 2>> dp[N];
ll udp[N];
void ubaci(int s, array<ll, 2> f) {
    if (dp[s].size() == 3 && f[0] < dp[s][2][0])    return;
    if (dp[s].size() == 3)  dp[s].pop_back();
    dp[s].pb(f);
    for (int i = dp[s].size()-1; i >= 1; --i) {
        if (dp[s][i] > dp[s][i-1])  swap(dp[s][i], dp[s][i-1]);
    }
}
void dfs(int s) {
    for (auto [u, w] : g[s]) {
        dfs(u);
        if (dp[u].empty())  ubaci(s, {w, u});
        else
            ubaci(s, {w+dp[u][0][0], u});
    }
}
void dfs2(int s) {
    for (auto [u, w] : g[s]) {
        if (dp[s].size() && dp[s][0][1] == u) {
            udp[u] = udp[s]+w;
            if (dp[s].size() > 1)   udp[u] = max(udp[u], dp[s][1][0]+w);
        }
        else
            udp[u] = max(udp[s]+w, dp[s][0][0]+w);
        dfs2(u);
    }
}
int tin[N], tout[N], tmr;
ll lz[4*N], st[4*N];
void dfs3(int s) {
    tin[s] = ++tmr;
    for (auto [u, w] : g[s]) {
        dfs3(u);
    }
    tout[s] = tmr;
}
int nn;
void push(int i) {
    if (!lz[i]) return;
    st[2*i] += lz[i];
    st[2*i+1] += lz[i];
    lz[2*i] += lz[i];
    lz[2*i+1] += lz[i];
    lz[i] = 0;
}
void upd(int l, int r, int x, int i = 1, int l2 = 1, int r2 = nn) {
    if (l <= l2 && r2 <= r) {
        st[i] += x;
        lz[i] += x;
        return;
    }
    push(i);
    int m2 = (l2+r2)/2;
    if (l <= m2)
        upd(l, r, x, 2*i, l2, m2);
    if (m2+1 <= r)
        upd(l, r, x, 2*i+1, m2+1, r2);
    st[i] = max(st[2*i], st[2*i+1]);
}
ll qry(int l, int r, int i = 1, int l2 = 1, int r2 = nn) {
    if (l <= l2 && r2 <= r) return st[i];
    int m2 = (l2+r2)/2;
    ll S = 0;
    if (l <= m2)
        S = max(S, qry(l, r, 2*i, l2, m2));
    if (m2+1 <= r)
        S = max(S, qry(l, r, 2*i+1, m2+1, r2));
    return S;
}
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)    g[p[i]].insert({i, w[i]});
    int mx = 0;
    for (int i = 1; i <= n; ++i)    mx = max(mx, (int)g[i].size());
    if ((g[1].size() == n-1) || (mx == n-2 && g[1].size() == 1)) {
        multiset<int> st;
        for (int i = 2; i <= n; ++i)    st.insert(w[i]);
        for (int i = 1; i <= q; ++i) {
            st.erase(st.find(w[s[i]]));
            st.insert(k[i]);
            w[s[i]] = k[i];
            auto it = st.rbegin();
            for (int j = 1; j <= 3; ++j) {
                ans[i] += *it;
                if (j != 3) it++;
            }
        }
        return;
    }
    if (q*(1LL)*n > 5000*5000) {
        dfs3(1);
        set<array<int, 2>> lw;
        multiset<ll> ms;
        for (int i = 2; i <= n; ++i) {
            upd(tin[i], tout[i], w[i]);
        }
        for (auto [u, w] : g[1]) {
            ms.insert(qry(tin[u], tout[u]));
            lw.insert({tout[u], u});
        }
        for (int i = 1; i <= q; ++i) {
            //cout << '\n';
            //cout << i << "A" << endl;
            int u = (*lw.lower_bound({tout[s[i]], 0}))[1];
            //cout << i << ' ' << u << "x" << '\n';
            ms.erase(ms.find(qry(tin[u], tout[u])));
            //cout << i << "y" << endl;
            upd(tin[s[i]], tout[s[i]], k[i]-w[s[i]]);
            //cout << i << "z" << endl;
            ms.insert(qry(tin[u], tout[u]));
            //cout << i << "t" << endl;
            w[s[i]] = k[i];
            auto it = ms.rbegin();
            //for (auto z : ms)   cout << z << 't';
            //cout << '\n';
            ans[i] = 0;
            for (int j = 1; j <= 3; ++j) {
                //cout << *it << '\n';
                ans[i] += *it;
                if (j != 3) it++;
            }
            //cout << i << "B" << endl;
        }
        return;
    }
    for (int i = 1; i <= q; ++i) {
        g[p[s[i]]].erase({s[i], w[s[i]]});
        w[s[i]] = k[i];
        g[p[s[i]]].insert({s[i], w[s[i]]});
        for (int i = 1; i <= n; ++i) {
            dp[i].clear();
            udp[i] = 0;
        }
        dfs(1);
        dfs2(1);
        //cout << endl << endl << endl;
        ans[i] = 0;
        for (int j = 2; j <= n; ++j)    ubaci(j, {udp[j], p[j]});
        for (int j = 1; j <= n; ++j) {
            if (dp[j].size() == 3) {
                ll s = 0;
                for (auto [w, u] : dp[j])   s += w;
                ans[i] = max(ans[i], s);
            }
        }
    }
}
/*
4 2
0 1 1 1
0 1 2 3
2 3
10 20

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

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