#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 5e5+5;
set<array<ll, 2>> dp[N], g[N];
ll udp[N];
void dfs(int s, int e = -1) {
    for (auto [u, w] : g[s]) {
        dfs(u, s);
        if (dp[u].empty())  dp[s].insert({w, u});
        else
            dp[s].insert({w+(*dp[u].rbegin())[0], u});
        if (dp[s].size() > 3)   dp[s].erase(dp[s].begin());
    }
}
void dfs2(int s, int e = -1) {
    for (auto [u, w] : g[s]) {
        if (dp[s].size() && (*dp[s].rbegin())[1] == u) {
            array<ll, 2> f = *dp[s].rbegin();
            dp[s].erase(f);
            udp[u] = udp[s]+w;
            if (dp[s].size())   udp[u] = max(udp[u], (*dp[s].rbegin())[0]+w);
            dp[s].insert(f);
        }
        else
            udp[u] = max(udp[s]+w, (*dp[s].rbegin())[0]+w);
        dfs2(u, s);
    }
}
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]});
    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;
        }
        /*for (int i = 1; i <= n; ++i) {
            cout << i << ":";
            for (auto [u, w] : g[i])    cout << u << ' ' << w << '-';
            cout << endl;
        }*/
        dfs(1);
        dfs2(1);
        /*for (int i = 1; i <= n; ++i) {
            cout << i << ' ' << udp[i] << ":";
            for (auto [u, w] : dp[i])    cout << u << ' ' << w << '-';
            cout << endl;
        }
        cout << endl << endl << endl;*/
        ans[i] = 0;
        for (int j = 2; j <= n; ++j)    dp[j].insert({udp[j], p[j]});
        for (int j = 1; j <= n; ++j) {
            while (dp[j].size() > 3)    dp[j].erase(dp[j].begin());
            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
*/