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

vector<vector<pair<int, ll>>> l;

ll dfs(int node, int parent) {
	ll res = 0;
	for(auto i : l[node]) {
		if(i.first == parent)
			continue;
		res = max(res, dfs(i.first, node) + i.second);
	}
	return res;
}

ll nadji_najbolje(int node) {
	ll res3 = 0, res2 = 0, res1 = 0;
	for(auto i : l[node]) {
		ll val = dfs(i.first, node) + i.second;
		if(val > res1) {
			res3 = res2;
			res2 = res1;
			res1 = val;
		}
		else if(val > res2) {
			res3 = res2;
			res2 = val;
		}
		else if(val > res3) {
			res3 = val;
		}
	}
	return res1 + res2 + res3;
}

void Bumerang(int n, int q, int* p, int* w, int* s, int* k, long long* ans) {
	l.resize(n+1);
	int deg1 = 0, deg2 = 0;
	for(int i = 1; i <= n; i++) {
		l[i].emplace_back(p[i], w[i]);
		l[p[i]].emplace_back(i, w[i]);
	}
	for(int i = 1; i <= n; i++) {
		if(l[i].size() > deg1) {
			deg2 = deg1;
			deg1 = l[i].size();
		}
		else if(l[i].size() > deg2) {
			deg2 = l[i].size();
		}
	}
	if(deg2 == 1) {
		multiset<ll> link;
		for(int i = 1; i <= n; i++)
			link.insert(w[i]);
		for(int i = 1; i <= q; i++) {
			link.erase(link.find(w[s[i]]));
			link.insert(k[i]);
			w[s[i]] = k[i];
			ll res = 0;
			auto it = link.rbegin();
			res += *it;
			it++;
			res += *it;
			it++;
			res += *it;
			ans[i] = res;
		}
	}
	else {
		for(int i = 1; i <= q; i++) {
			for(int j = 0; j < l[s[i]].size(); j++) {
				if(l[s[i]][j] == make_pair(p[s[i]], w[s[i]])) {
					l[s[i]].erase(l[s[i]].begin() + j);
					break;
				}
			}
			l[s[i]].emplace_back(p[s[i]], k[i]);
			for(int j = 0; j < l[p[s[i]]].size(); j++) {
				if(l[p[s[i]]][j] == make_pair(s[i], w[s[i]])) {
					l[p[s[i]]].erase(l[p[s[i]]].begin() + j);
					break;
				}
			}
			l[p[s[i]]].emplace_back(s[i], k[i]);
			w[s[i]] = k[i];
			ll res = 0;
			for(int i = 1; i <= n; i++) {
				res = max(res, nadji_najbolje(i));
			}
			ans[i] = res;
		}
	}
}