#include <bits/stdc++.h>
using namespace std;
using lint = long long;
const lint INF = 1e18;
const lint MOD = 1e9 + 7;
class SegTree {
public:
int sz;
vector<int> cnt;
vector<lint> tree;
vector<lint> lazy;
SegTree(int sz) : sz(sz), cnt(2 * sz), tree(2 * sz), lazy(2 * sz) {
Build(1, 0, sz - 1);
}
void Build(int n, int tl, int tr) {
if (tl == tr) {
cnt[n] = 1;
tree[n] = 0;
lazy[n] = 0;
return;
}
int md = (tl + tr) / 2;
int z = n + 2 * (md - tl + 1);
Build(n + 1, tl, md);
Build(z, md + 1, tr);
Pull(n, n + 1, z);
}
void Pull(int n, int lc, int rc) {
cnt[n] = cnt[lc] + cnt[rc];
tree[n] = tree[lc] + tree[rc];
if (cnt[n] > 1) {
tree[n] %= MOD;
}
}
void Apply(int n, lint x) {
tree[n] += cnt[n] * x;
lazy[n] += x;
if (cnt[n] > 1) {
tree[n] %= MOD;
}
}
void Push(int n, int lc, int rc) {
Apply(lc, lazy[n]);
Apply(rc, lazy[n]);
lazy[n] = 0;
}
void Update(int n, int tl, int tr, int l, int r, lint x) {
if (l > tr || tl > r || tl > tr || l > r) return;
if (l <= tl && tr <= r) return Apply(n, x);
int md = (tl + tr) / 2;
int z = n + 2 * (md - tl + 1);
Push(n, n + 1, z);
Update(n + 1, tl, md, l, r, x);
Update(z, md + 1, tr, l, r, x);
Pull(n, n + 1, z);
}
void Update(int l, int r, lint x) {
Update(1, 0, sz - 1, l, r, x);
}
lint Query(int p) {
int n = 1, tl = 0, tr = sz - 1;
while (tl != tr) {
int md = (tl + tr) / 2;
int z = n + 2 * (md - tl + 1);
Push(n, n + 1, z);
if (p <= md) {
n = n + 1;
tr = md;
} else {
n = z;
tl = md + 1;
}
}
assert(tl == tr);
return tree[n];
}
lint Query() {
return tree[1];
}
};
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
vector<int> st(N);
vector<int> ist(N);
vector<int> siz(N);
vector<int> par(N);
vector<int> root(N);
vector<int> depth(N);
vector<vector<int>> adj(N);
par[0] = -1;
for (int i = 1; i < N; i++) {
cin >> par[i];
adj[par[i]].emplace_back(i);
}
const auto DfsInit = [&](const auto &self, int u) -> void {
siz[u] = 1;
for (auto &v : adj[u]) {
depth[v] = depth[u] + 1;
self(self, v);
siz[u] += siz[v];
if (siz[v] > siz[adj[u][0]]) {
swap(v, adj[u][0]);
}
}
};
const auto DfsHld = [&](const auto &self, int u) -> void {
static int timer = 0;
st[u] = timer++;
ist[st[u]] = u;
for (auto v : adj[u]) {
root[v] = v == adj[u][0] ? root[u] : v;
self(self, v);
}
};
DfsInit(DfsInit, 0);
DfsHld(DfsHld, 0);
// Complexity by Link-Cut Tree Heavy-Light analysis
// Keep segment tree, with dp[v] on position v
// Update link-cut style on HLD
// Time: O((N + Q) log^2 N).
set<int> chain;
for (int i = 0; i < N; i++) {
chain.emplace(st[i]);
}
const auto ModifyChain = [&](int u, int sgn) {
if (sgn == -1) {
chain.erase(chain.find(st[u]));
} else if (sgn == +1) {
chain.emplace(st[u]);
}
};
SegTree dp_1(N);
SegTree dp_2(N);
vector<int> prefer(N, -1);
vector<lint> weight(N);
const auto Update = [&](const auto &self, int prv) -> void {
if (prv == 0) return;
int u = par[prv];
lint newdp = dp_1.Query(st[prv]) + weight[prv];
if (newdp <= dp_2.Query(st[u])) {
// do nothing
} else if (dp_2.Query(st[u]) < newdp && newdp <= dp_1.Query(st[u])) {
dp_2.Update(st[u], st[u], newdp - dp_2.Query(st[u]));
} else if (dp_1.Query(st[u]) < newdp) {
lint dp1 = dp_1.Query(st[u]);
lint dp2 = dp_2.Query(st[u]);
int head = ist[*prev(chain.upper_bound(st[u]))];
assert(root[u] == root[head]);
if (prefer[u] == prv) {
dp_1.Update(st[head], st[u], newdp - dp1);
return self(self, head);
}
if (prefer[u] != -1) {
// insert prefer[u] as head chain
ModifyChain(prefer[u], +1);
prefer[u] = -1;
}
prefer[u] = prv;
if (root[u] == root[prv]) {
// delete prv as head chain
ModifyChain(prv, -1);
}
dp_2.Update(st[u], st[u], dp1 - dp2);
dp_1.Update(st[head], st[u], newdp - dp1);
return self(self, head);
}
};
const auto Print = [&]() {
for (int i = 0; i < N; i++) {
cout << i << ' ' << dp_1.Query(st[i]) << ' ' << dp_2.Query(st[i]) << '\n';
}
cout << '\n';
};
for (int i = 1; i < N; i++) {
int w;
cin >> w;
weight[i] += w;
Update(Update, i);
}
cout << (dp_1.Query() + dp_2.Query()) % MOD << '\n';
int Q;
cin >> Q;
while (Q--) {
int u, w;
cin >> u >> w;
weight[u] += w;
Update(Update, u);
cout << (dp_1.Query() + dp_2.Query()) % MOD << '\n';
// Print();
}
return 0;
}
Compilation message
arboras.cpp: In function 'int main()':
arboras.cpp:200:14: warning: variable 'Print' set but not used [-Wunused-but-set-variable]
200 | const auto Print = [&]() {
| ^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
460 KB |
Output is correct |
| 2 |
Correct |
3 ms |
460 KB |
Output is correct |
| 3 |
Correct |
3 ms |
460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1633 ms |
23408 KB |
Output is correct |
| 2 |
Correct |
311 ms |
21720 KB |
Output is correct |
| 3 |
Correct |
344 ms |
21956 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1290 ms |
24700 KB |
Output is correct |
| 2 |
Correct |
623 ms |
25640 KB |
Output is correct |
| 3 |
Correct |
436 ms |
22880 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
6 ms |
460 KB |
Output is correct |
| 2 |
Correct |
3 ms |
460 KB |
Output is correct |
| 3 |
Correct |
3 ms |
460 KB |
Output is correct |
| 4 |
Correct |
1633 ms |
23408 KB |
Output is correct |
| 5 |
Correct |
311 ms |
21720 KB |
Output is correct |
| 6 |
Correct |
344 ms |
21956 KB |
Output is correct |
| 7 |
Correct |
1290 ms |
24700 KB |
Output is correct |
| 8 |
Correct |
623 ms |
25640 KB |
Output is correct |
| 9 |
Correct |
436 ms |
22880 KB |
Output is correct |
| 10 |
Correct |
1384 ms |
24492 KB |
Output is correct |
| 11 |
Correct |
617 ms |
25360 KB |
Output is correct |
| 12 |
Correct |
548 ms |
22896 KB |
Output is correct |
| 13 |
Correct |
1059 ms |
25824 KB |
Output is correct |
| 14 |
Correct |
1004 ms |
26316 KB |
Output is correct |
