#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 hld[N];
int sz[N];
int tin[N], tout[N];
int sum = 0;
int fen[N];
vector<int> ord;
int ind[4 * N];
void upd(int v, int vl, int vr, int pos, int val) {
if (vr - vl == 1) {
ind[v] = val == 0 ? vl : -1;
} else {
int vm = (vl + vr) / 2;
if (pos < vm) {
upd(2 * v, vl, vm, pos, x);
} else {
upd(2 * v + 1, vm, vr, pos, x);
}
ind[v] = max(ind[2 * v], ind[2 * v + 1]);
}
}
int get_ind(int v, int vl, int vr, int l, int r) {
if (vl >= r || vr <= l) return -1;
if (vl >= l && vr <= r) return ind[v];
int vm = (vl + vr) / 2;
return max(get_ind(2 * v, vl, vm, l, r), get_ind(2 * v + 1, vm, vr, l, r));
}
void build(int v, int vl, int vr) {
if (vr - vl == 1) {
ind[v] = vl;
} else {
int vm = (vl + vr) / 2;
build(2 * v, vl, vm);
build(2 * v + 1, vm, vr);
ind[v] = max(ind[2 * v], ind[2 * v + 1]);
}
}
bool is_par(int v, int u) {
return tin[v] <= tin[u] && tout[v] >= tout[u];
}
int top(int v) {
while (v != 0 && best[p[v]] == v) v = p[v];
return v;
/*while (v != -1) {
int i = get_ind(1, 0, n, tin[hld[v]], tin[v] + 1);
if (i != -1) return ord[i];
v = p[hld[v]];
}
assert(0);
return -1;*/
}
void add_fen(int pos, int val) {
for (int i = pos + 1; i < N; i += i & -i) fen[i] += val;
}
void add_fen(int l, int r, int val) {
sum += (r - l) * val;
add_fen(l, val);
add_fen(r, -val);
}
int get_fen(int r) {
int res = 0;
for (; r > 0; r -= r & -r) res += fen[r];
return res;
}
void add_path(int v, int u, int val) {
while (u != -1 && is_par(v, u)) {
if (is_par(v, hld[u])) {
add_fen(tin[hld[u]], tin[u] + 1, val);
} else {
add_fen(tin[v], tin[u] + 1, val);
}
u = p[hld[u]];
}
}
int get_dp(int v) {
return get_fen(tin[v] + 1);
}
void dfs(int v) {
best[v] = best2[v] = -1;
dp[v] = dp2[v] = 0;
sz[v] = 1;
for (int u : g[v]) {
dfs(u);
sz[v] += sz[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;
}
}
if (best[v] == -1 && !g[v].empty()) best[v] = g[v][0];
if (best2[v] == -1 && g[v].size() >= 2) best2[v] = g[v][1];
sum += dp2[v];
}
void dfs1(int v) {
tin[v] = ord.size();
ord.push_back(v);
for (int &u : g[v]) {
if (sz[u] > sz[g[v][0]]) swap(g[v][0], u);
}
for (int u : g[v]) {
hld[u] = u == g[v][0] ? hld[v] : u;
dfs1(u);
}
tout[v] = ord.size();
}
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);
dfs1(0);
for (int i = 0; i < n; ++i) add_path(i, i, dp[i]);
build(1, 0, n);
for (int i = 1; i < n; ++i) {
if (i == best[p[i]]) upd(1, 0, n, tin[i], 1);
}
cout << sum % md << "\n";
cin >> q;
//int query_id = 0;
while (q--) {
int v, add;
cin >> v >> add;
d[v] += add;
if (v == best[p[v]]) {
add_path(top(v), p[v], add);
/*cout << "query_id: " << query_id << endl;
cout << "top: " << top(v) << endl;
cout << "bottom: " << p[v] << endl;
cout << "sum: " << sum << endl;*/
v = top(v);
}
while (v != 0) {
if (get_dp(v) + d[v] > get_dp(p[v])) {
sum += get_dp(p[v]) - dp2[p[v]];
dp2[p[v]] = get_dp(p[v]), best2[p[v]] = best[p[v]];
upd(1, 0, n, tin[best[p[v]]], 0);
upd(1, 0, n, tin[v], 1);
best[p[v]] = v;
add_path(top(p[v]), p[v], get_dp(v) + d[v] - get_dp(p[v]));
} else {
if (get_dp(v) + d[v] > dp2[p[v]]) {
sum += get_dp(v) + d[v] - dp2[p[v]];
dp2[p[v]] = get_dp(v) + d[v], best2[p[v]] = v;
}
break;
}
v = top(p[v]);
}
/*cout << "top: ";
for (int i = 0; i < n; ++i) cout << top(i) << " ";
cout << endl;
cout << "best: ";
for (int i = 0; i < n; ++i) cout << best[i] << " ";
cout << endl;*/
cout << sum % md << "\n";
//++query_id;
}
return 0;
}
Compilation message
arboras.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int)':
arboras.cpp:28:37: error: 'x' was not declared in this scope
28 | upd(2 * v, vl, vm, pos, x);
| ^
arboras.cpp:30:41: error: 'x' was not declared in this scope
30 | upd(2 * v + 1, vm, vr, pos, x);
| ^
