제출 #422868

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
422868		valerikk	Arboras (RMI20_arboras)	C++17	24 / 100	537 ms	14136 KiB

arboras

#include <bits/stdc++.h>

using namespace std;
#define int long long

const int N = 1e5 + 7;
const int md = 1e9 + 7;

int n, q;
int p[N], d[N];
vector<int> g[N];
int best[N], best2[N];
int dp[N], dp2[N];
int sum = 0;

void dfs(int v) {
	best[v] = best2[v] = -1;
	dp[v] = dp2[v] = 0;
	for (int u : g[v]) {
		dfs(u);
		if (dp[u] + d[u] > dp[v]) {
			dp2[v] = dp[v], best2[v] = best[v];
			dp[v] = dp[u] + d[u], best[v] = u;
		} else if (dp[u] + d[u] > dp2[v]) {
			dp2[v] = dp[u] + d[u];
			best2[v] = u;
		}
	}
	sum += dp[v] + dp2[v];
}

signed main() {
#ifdef LOCAL
	freopen("input.txt", "r", stdin);
#endif
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n;
	p[0] = -1;
	for (int i = 1; i < n; ++i) {
		cin >> p[i];
		g[p[i]].push_back(i);
	}
	for (int i = 1; i < n; ++i) {
		cin >> d[i];
	}
	dfs(0);
	cout << sum << "\n";
	cin >> q;
	while (q--) {
		int v, add;
		cin >> v >> add;
		d[v] += add;
		while (v != 0) {
			if (v == best[p[v]]) {
				sum += dp[v] + d[v] - dp[p[v]];
				dp[p[v]] = dp[v] + d[v];
			} else if (dp[v] + d[v] > dp[p[v]]) {
				sum += dp[p[v]] - dp2[p[v]] + dp[v] + d[v] - dp[p[v]];
				dp2[p[v]] = dp[p[v]], best[p[v]] = best2[p[v]];
				dp[p[v]] = dp[v] + d[v], best[p[v]] = v;
			} else {
				if (dp[v] + d[v] > dp2[p[v]]) {
					sum += dp[v] + d[v] - dp2[p[v]];
					dp2[p[v]] = dp[v] + d[v], best2[p[v]] = v;
				}
				break;
			}
			v = p[v];
		}
		cout << sum % md << "\n";
	}
	return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 13 / 13
• Subtask 3: 0 / 31
• Subtask 4: 0 / 45