#include <bits/stdc++.h>
#define x first
#define u second
#define ll long long
#define ii pair <ll, int>
using namespace std;
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
ll sumDep, sumMax, sumSec;
int n, q;
int par[N], cntDep[N], top[N];
int tin[N], tout[N], order[N], timer;
ll dep[N];
vector<int> G[N];
int getSurroundChild(int u, int v) {
int lo = 0, hi = int(G[u].size()) - 1;
while (lo < hi) {
int md = (lo + hi + 1) >> 1;
if (tin[v] < tin[G[u][md]]) hi = md - 1;
else lo = md;
}
return G[u][lo];
}
ii st[N << 2];
ll lz[N << 2];
void build(int rt, int lo, int hi) {
if (lo == hi) return st[rt] = ii(dep[order[lo]], order[lo]), lz[rt] = 0, void(0);
int md = (lo + hi) >> 1, lc = rt << 1, rc = lc | 1;
build(lc, lo, md), build(rc, md + 1, hi);
st[rt] = max(st[lc], st[rc]), lz[rt] = 0;
}
void modify(int l, int r, ll x, int rt, int lo, int hi) {
if (hi < l || r < lo) return;
if (l <= lo && hi <= r) return st[rt].x += x, lz[rt] += x, void(0);
int md = (lo + hi) >> 1, lc = rt << 1, rc = lc | 1;
modify(l, r, x, lc, lo, md);
modify(l, r, x, rc, md + 1, hi);
st[rt] = max(st[lc], st[rc]), st[rt].x += lz[rt];
}
ii getST(int l, int r, int rt, int lo, int hi) {
if (hi < l || r < lo) return ii(0, 0);
if (l <= lo && hi <= r) return st[rt];
int md = (lo + hi) >> 1, lc = rt << 1, rc = lc | 1;
auto ver = max(getST(l, r, lc, lo, md), getST(l, r, rc, md + 1, hi));
ver.x += lz[rt];
return ver;
}
ii getMaxDep(int u) {
return getST(tin[u], tout[u], 1, 1, N);
}
ii getSecDep(int u) {
int mx = getMaxDep(u).u;
if ((int) G[u].size() <= 1) return getST(tin[u], tin[u], 1, 1, N);
int v = getSurroundChild(u, mx);
return max(getST(tin[u], tin[v] - 1, 1, 1, N), getST(tout[v] + 1, tout[u], 1, 1, N));
}
int high[N], mxhigh = 0;
void dfs(int u) {
tin[u] = ++timer;
order[tin[u]] = u;
for (int v : G[u]) {
cntDep[v] = cntDep[u] + 1;
dep[v] += dep[u];
high[v] = high[u] + 1;
mxhigh = max(mxhigh, high[v]);
dfs(v);
}
tout[u] = timer;
}
void solve(){
cin >> n;
for (int u = 2; u <= N; ++u) {
cin >> par[u];
++par[u];
G[par[u]].push_back(u);
}
dep[1] = 1;
bool ck = true;
for (int u = 2; u <= N; ++u) {
cin >> dep[u];
if (dep[u] != 1e9) ck = false;
}
high[1] = 1;
dfs(1);
build(1, 1, N);
sumDep = 0, sumMax = 0, sumSec = 0;
for (int u = 1; u <= N; ++u) top[u] = u;
for (int u = 1; u <= N; ++u) {
sumDep += dep[u];
sumMax += dep[getMaxDep(u).u];
sumSec += dep[getSecDep(u).u];
int mx = getMaxDep(u).u;
if (cntDep[top[mx]] > cntDep[u]) top[mx] = u;
}
cout << (sumMax + sumSec - 2 * sumDep) % mod << '\n';
cin >> q;
while (q --) {
int u; ll x;
cin >> u >> x;
++u;
sumDep += (tout[u] - tin[u] + 1) * x;
sumMax += (tout[u] - tin[u] + 1) * x;
sumSec += (tout[u] - tin[u] + 1) * x;
ii mx = getST(tin[u], tout[u], 1, 1, N);
mx.x += x;
sumMax += (cntDep[u] - cntDep[top[mx.u]]) * x;
while (true) {
int curTop = top[mx.u];
if (curTop == 1) break;
int p = par[curTop];
ii ve = getMaxDep(p);
if (ve > mx) {
ii tmp = getSecDep(p);
if (tmp < mx) sumSec += mx.x - tmp.x;
break;
} else {
sumSec += ve.x - getSecDep(p).x;
int newTop = top[ve.u];
sumMax += (cntDep[curTop] - cntDep[newTop]) * (mx.x - ve.x);
top[ve.u] = getSurroundChild(p, ve.u);
top[mx.u] = newTop;
}
}
if (n * q <= 1e7 || mxhigh <= 100 || ck) cout << (sumMax + sumSec - 2 * sumDep) % mod << '\n';
modify(tin[u], tout[u], x, 1, 1, N);
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}
Compilation message
arboras.cpp: In function 'void solve()':
arboras.cpp:94:12: warning: iteration 100003 invokes undefined behavior [-Waggressive-loop-optimizations]
94 | if (dep[u] != 1e9) ck = false;
| ~~~~~^
arboras.cpp:92:20: note: within this loop
92 | for (int u = 2; u <= N; ++u) {
| ^
arboras.cpp:102:38: warning: iteration 100004 invokes undefined behavior [-Waggressive-loop-optimizations]
102 | for (int u = 1; u <= N; ++u) top[u] = u;
| ^
arboras.cpp:102:20: note: within this loop
102 | for (int u = 1; u <= N; ++u) top[u] = u;
| ^
arboras.cpp:104:18: warning: iteration 100004 invokes undefined behavior [-Waggressive-loop-optimizations]
104 | sumDep += dep[u];
| ~~~~~^
arboras.cpp:103:20: note: within this loop
103 | for (int u = 1; u <= N; ++u) {
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
9048 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
73 ms |
35304 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
20 ms |
14168 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
9048 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
