#include <bits/stdc++.h>
using namespace std;
#ifdef ngu
#include "debug.h"
#else
#define debug(...) 42
#endif
using ll = int64_t;
const int N = 1e5 + 5, MOD = 1e9 + 7;
int n, q;
int p[N], tin[N], tout[N], pos[N], head[N], h[N];
ll d[N];
vector<int> g[N];
using Node = pair<ll, int>;
ll lz[4 * N];
Node s[4 * N];
void bld(int id = 1, int l = 1, int r = n) {
if (l == r) {
s[id] = {d[pos[l]], pos[l]};
return;
}
int md = (l + r) / 2;
bld(id * 2, l, md);
bld(id * 2 + 1, md + 1, r);
s[id] = max(s[id * 2], s[id * 2 + 1]);
}
void app(int id, ll x) {
s[id].first += x;
lz[id] += x;
}
void psh(int id) {
app(id * 2, lz[id]);
app(id * 2 + 1, lz[id]);
lz[id] = 0;
}
void upd(int u, int v, ll x, int id = 1, int l = 1, int r = n) {
if (u <= l && r <= v) {
app(id, x);
return;
}
if (lz[id]) {
psh(id);
}
int md = (l + r) / 2;
if (u <= md) {
upd(u, v, x, id * 2, l, md);
}
if (md < v) {
upd(u, v, x, id * 2 + 1, md + 1, r);
}
s[id] = max(s[id * 2], s[id * 2 + 1]);
}
Node get(int u, int v, int id = 1, int l = 1, int r = n) {
if (u <= l && r <= v) {
return s[id];
}
if (lz[id]) {
psh(id);
}
int md = (l + r) / 2;
if (u <= md && md < v) {
return max(get(u, v, id * 2, l, md), get(u, v, id * 2 + 1, md + 1, r));
}
if (md < u) {
return get(u, v, id * 2 + 1, md + 1, r);
}
return get(u, v, id * 2, l, md);
}
int getc(int u, int x) {
if (u == x) {
return u;
}
int l = 0, r = g[u].size() - 1, res = 0;
while (l <= r) {
int md = (l + r) / 2;
if (tin[x] <= tout[g[u][md]]) {
res = g[u][md];
r = md - 1;
} else {
l = md + 1;
}
}
return res;
}
ll getsec(int u, int s) {
ll res = 0;
if (tin[u] < tin[s]) {
res = max(res, get(tin[u], tin[s] - 1).first);
}
if (tout[s] < tout[u]) {
res = max(res, get(tout[s] + 1, tout[u]).first);
}
return res;
}
int order;
void dfs(int u = 1) {
pos[tin[u] = ++order] = u;
for (int v : g[u]) {
d[v] += d[u];
h[v] = h[u] + 1;
dfs(v);
}
tout[u] = order;
}
void add(int &x, int y) {
if ((x += y) >= MOD) {
x -= MOD;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
#ifdef ngu
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
#endif
cin >> n;
for (int i = 2; i <= n; ++i) {
cin >> p[i];
g[++p[i]].emplace_back(i);
}
for (int i = 2; i <= n; ++i) {
cin >> d[i];
}
dfs();
bld();
int res = 0;
for (int i = n; i >= 1; --i) {
int j = get(tin[i], tout[i]).second;
add(res, (d[j] - d[i]) % MOD);
ll s = getsec(i, getc(i, j));
if (s >= d[i]) {
add(res, (s - d[i]) % MOD);
}
head[j] = i;
}
cout << res << "\n";
cin >> q;
while (q--) {
if (clock() > 2100) {
cout << "TLE\n";
exit(0);
}
int v;
ll a;
cin >> v >> a;
v++;
int x = v, y = a;
auto [best, id] = get(tin[v], tout[v]);
best += a;
while (v > 1) {
int u = head[id];
add(res, ll(h[v] - h[u]) * a % MOD);
v = u;
u = p[v];
if (u) {
auto [nbest, nid] = get(tin[u], tout[u]);
ll s = getc(u, nid);
ll sec = getsec(u, s);
if (best > sec) {
add(res, (best - sec) % MOD);
if (make_pair(best, id) > make_pair(nbest, nid)) {
head[id] = head[nid];
head[nid] = s;
a = best - nbest;
v = u;
} else {
break;
}
} else {
break;
}
}
}
upd(tin[x], tout[x], y);
cout << res << "\n";
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
13964 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
36 ms |
15840 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
6660 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
