#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 = 5e5+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);
    }
}
void Bumerang(int n, int q, int* p, int* w, int* s, int* k, long long* ans){
    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 (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;
    }
    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
*/