#include <bits/stdc++.h>
using namespace std;
const int kN = 1e5;
const int mod = 1e9 + 7;
vector<int> g[1 + kN];
int depth[1 + kN], bestSon[1 + kN], ans;
int64_t max1[1 + kN], max2[1 + kN];
struct edge {
int par;
int64_t len;
} edges[1 + kN];
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct treapNode {
treapNode* l;
treapNode* r;
treapNode* par;
int node, prior, sz;
int64_t maxChain, lazy;
};
using ptr = treapNode*;
using pt = pair<ptr, ptr>;
ptr emptyNode = new treapNode{nullptr, nullptr, nullptr, 0, -1, 0, 0, 0};
ptr roots[1 + kN];
inline void updateNode(ptr node) {
if (node != emptyNode) {
node->sz = 1 + node->l->sz + node->r->sz;
node->par = nullptr;
if (node->l != emptyNode) {
node->l->par = node;
}
if (node->r != emptyNode) {
node->r->par = node;
}
}
}
inline void incNode(ptr node, const int64_t &val) {
node->maxChain += val;
node->lazy += val;
}
inline void push(ptr node) {
if (node != emptyNode && node->lazy != 0) {
if (node->l != emptyNode) {
incNode(node->l, node->lazy);
}
if (node->r != emptyNode) {
incNode(node->r, node->lazy);
}
node->lazy = 0;
}
}
pt split(ptr node, const int &k) {
if (node == emptyNode) {
return {emptyNode, emptyNode};
}
push(node);
if (node->l->sz < k) {
pt p = split(node->r, k - node->l->sz - 1);
node->r = p.first;
updateNode(node);
return {node, p.second};
}
pt p = split(node->l, k);
node->l = p.second;
updateNode(node);
return {p.first, node};
}
ptr join(ptr A, ptr B) {
if (A == emptyNode) {
return B;
}
if (B == emptyNode) {
return A;
}
push(A);
push(B);
if (B->prior < A->prior) {
A->r = join(A->r, B);
updateNode(A);
return A;
}
B->l = join(A, B->l);
updateNode(B);
return B;
}
int getNode(ptr node, const int &k) {
if (node == emptyNode) {
return 0;
}
if (node->l->sz == k - 1) {
return node->node;
}
push(node);
if (k <= node->l->sz) {
return getNode(node->l, k);
}
return getNode(node->r, k - node->l->sz - 1);
}
inline int findRoot(ptr node) {
ptr root = node;
while (root->par) {
root = root->par;
}
return root->node;
}
inline int findChainTop(ptr node) {
ptr root = roots[findRoot(node)];
while (root->l != emptyNode) {
root = root->l;
}
return root->node;
}
inline void maxSelf(int64_t &x, const int64_t &y) {
if (x < y) {
x = y;
}
}
inline int norm(int64_t x) {
if (x >= mod) {
x %= mod;
}
return x;
}
inline void addSelf(int &x, const int &y) {
x += y;
if (x < 0) {
x += mod;
}
if (x >= mod) {
x -= mod;
}
}
inline int mult(const int64_t &x, const int &y) {
return norm(x * y);
}
void dfs1(const int &u) {
for (const int &v : g[u]) {
depth[v] = depth[u] + 1;
dfs1(v);
int64_t chainLen = max1[v] + edges[v].len;
if (max1[u] < chainLen) {
max2[u] = max1[u];
max1[u] = chainLen;
bestSon[u] = v;
} else {
maxSelf(max2[u], chainLen);
}
}
}
void dfs2(const int &u, ptr node) {
addSelf(ans, norm(max1[u]));
addSelf(ans, norm(max2[u]));
if (bestSon[u] == 0) {
return;
}
node = join(node, roots[bestSon[u]]);
dfs2(bestSon[u], node);
for (int v : g[u]) {
if (v != bestSon[u]) {
dfs2(v, roots[v]);
}
}
}
void updateChainPreff(const int &node, const int64_t &k) {
int tRoot = findRoot(roots[node]);
int chainTop = findChainTop(roots[node]);
int preff = depth[node] - depth[chainTop] + 1;
addSelf(ans, mult(k, preff));
ptr upChain, downChain;
tie(upChain, downChain) = split(roots[tRoot], preff);
incNode(upChain, k);
join(upChain, downChain);
if (chainTop == 1) {
return;
}
int par = edges[chainTop].par;
int ptRoot = findRoot(roots[par]);
int pChainTop = findChainTop(roots[par]);
int preffPar = depth[par] - depth[pChainTop] + 1;
int son = getNode(roots[ptRoot], preffPar + 1);
getNode(roots[tRoot], 1);
int64_t inc = roots[chainTop]->maxChain + edges[chainTop].len - (roots[son]->maxChain + edges[son].len);
if (inc <= 0) {
addSelf(ans, -norm(max2[par]));
maxSelf(max2[par], roots[chainTop]->maxChain + edges[chainTop].len);
addSelf(ans, norm(max2[par]));
} else {
ptr upChain, downChain;
tie(upChain, downChain) = split(roots[ptRoot], preffPar);
join(upChain, roots[tRoot]);
addSelf(ans, -norm(max2[par]));
maxSelf(max2[par], roots[son]->maxChain + edges[son].len);
addSelf(ans, norm(max2[par]));
updateChainPreff(par, inc);
}
}
void testCase() {
int n;
cin >> n;
for (int v = 2; v <= n; ++v) {
int u;
cin >> u;
++u;
edges[v].par = u;
g[u].emplace_back(v);
}
for (int v = 2; v <= n; ++v) {
int d;
cin >> d;
edges[v].len = d;
}
dfs1(1);
for (int v = 1; v <= n; ++v) {
roots[v] = new treapNode{emptyNode, emptyNode, nullptr, v, rng() % mod, 1, max1[v], 0};
}
dfs2(1, roots[1]);
cout << ans << '\n';
int q;
cin >> q;
for (int i = 1; i <= q; ++i) {
int v, k;
cin >> v >> k;
++v;
edges[v].len += k;
if (v == findChainTop(roots[v])) {
int tRoot = findRoot(roots[v]);
int par = edges[v].par;
int ptRoot = findRoot(roots[par]);
int pChainTop = findChainTop(roots[par]);
int preff = depth[par] - depth[pChainTop] + 1;
int son = getNode(roots[ptRoot], preff + 1);
getNode(roots[tRoot], 1);
int64_t inc = roots[v]->maxChain + edges[v].len - (roots[son]->maxChain + edges[son].len);
if (inc <= 0) {
addSelf(ans, -norm(max2[par]));
maxSelf(max2[par], roots[v]->maxChain + edges[v].len);
addSelf(ans, norm(max2[par]));
} else {
ptr upChain, downChain;
tie(upChain, downChain) = split(roots[ptRoot], preff);
join(upChain, roots[tRoot]);
addSelf(ans, -norm(max2[par]));
maxSelf(max2[par], roots[son]->maxChain + edges[son].len);
addSelf(ans, norm(max2[par]));
updateChainPreff(par, inc);
}
} else {
updateChainPreff(edges[v].par, k);
}
cout << ans << '\n';
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int tests = 1;
for (int tc = 1; tc <= tests; ++tc) {
testCase();
}
return 0;
}
Compilation message
arboras.cpp: In function 'void testCase()':
arboras.cpp:236:70: warning: narrowing conversion of '(rng.std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::operator()() % ((std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type)((int)mod)))' from 'std::mersenne_twister_engine<long unsigned int, 32, 624, 397, 31, 2567483615, 11, 4294967295, 7, 2636928640, 15, 4022730752, 18, 1812433253>::result_type' {aka 'long unsigned int'} to 'int' [-Wnarrowing]
236 | roots[v] = new treapNode{emptyNode, emptyNode, nullptr, v, rng() % mod, 1, max1[v], 0};
| ~~~~~~^~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2764 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2812 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2820 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
127 ms |
16556 KB |
Output is correct |
| 2 |
Correct |
72 ms |
13364 KB |
Output is correct |
| 3 |
Correct |
58 ms |
13616 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
119 ms |
17956 KB |
Output is correct |
| 2 |
Correct |
115 ms |
19720 KB |
Output is correct |
| 3 |
Correct |
87 ms |
14796 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2764 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2812 KB |
Output is correct |
| 3 |
Correct |
2 ms |
2820 KB |
Output is correct |
| 4 |
Correct |
127 ms |
16556 KB |
Output is correct |
| 5 |
Correct |
72 ms |
13364 KB |
Output is correct |
| 6 |
Correct |
58 ms |
13616 KB |
Output is correct |
| 7 |
Correct |
119 ms |
17956 KB |
Output is correct |
| 8 |
Correct |
115 ms |
19720 KB |
Output is correct |
| 9 |
Correct |
87 ms |
14796 KB |
Output is correct |
| 10 |
Correct |
140 ms |
18464 KB |
Output is correct |
| 11 |
Correct |
105 ms |
19740 KB |
Output is correct |
| 12 |
Correct |
89 ms |
14824 KB |
Output is correct |
| 13 |
Correct |
99 ms |
21340 KB |
Output is correct |
| 14 |
Correct |
107 ms |
22084 KB |
Output is correct |
