#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
#define pb push_back
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define F first
#define S second
const int N = 1e5+5, M = 1e9+7;
int n, in[N], id = 0, sz[N], rin[N], dep[N];
vector<int> adj[N];
pair<ll, ll> mx[(1 << 18)];
ll lz[(1 << 18)], sd = 0, p[N][18], fr[N], in2[N];
ll sum[(1 << 18)], st[(1 << 18)], sum2[(1 << 18)], st2[(1 << 18)];
bool tak[(1 << 18)], tak2[(1 << 18)];
ll mul(ll a, ll b) {
return (a * b) % M;
}
ll add(ll a, ll b) {
a += b;
return (a >= M ? a-M : a);
}
ll sub(ll a, ll b) {
a -= b;
return (a < 0 ? a+M : a);
}
void prop(int l, int r, int x) {
mx[x].F += lz[x];
if (l != r) {
lz[x*2+1] += lz[x];
lz[x*2+2] += lz[x];
}
lz[x] = 0;
}
void upd(int li, int ri, int x, int l, int r, ll val) {
if (li >= l && ri <= r) {
lz[x] += val;
prop(li, ri, x);
return;
}
prop(li, ri, x);
if (li > r || ri < l)return;
int m = (li + ri) >> 1;
upd(li, m, x*2+1, l, r, val);
upd(m+1, ri, x*2+2, l, r, val);
mx[x] = max(mx[x*2+1], mx[x*2+2]);
}
pair<ll, ll> get(int li, int ri, int x, int l, int r) {
prop(li, ri, x);
if (li >= l && ri <= r)return mx[x];
if (li > r || ri < l)return {0, 0};
int m = (li + ri) >> 1;
return max(get(li, m, x*2+1, l, r), get(m+1, ri, x*2+2, l, r));
}
int lift(int u, int k) {
for (int i = 0; i < 18; i++) {
if ((k & (1 << i)))u = p[u][i];
}
return u;
}
int pr(int u, int v) {
return lift(v, dep[v]-dep[u]-1);
}
void init(int u) {
rin[id] = u;
in[u] = id++;
sz[u] = 1;
for (auto &v : adj[u]) {
p[v][0] = u;
for (int i = 1; i < n; i++) {
p[v][i] = p[p[v][i-1]][i-1];
}
dep[v] = dep[u]+1;
init(v);
sz[u] += sz[v];
}
}
void prop2(int l, int r, int x) {
if (tak[x]) {
if (tak2[x]) {
tak[x] = tak2[x] = false;
if (l != r) {
tak2[x*2+1] = tak2[x*2+2] = true;
}
} else {
if (l != r)tak[x*2+1] = tak[x*2+2] = true;
sum2[x] = sum[x];
}
}
if (~st[x]) {
sum[x] = mul(r-l+1, st[x]);
if (l != r) {
st[x*2+1] = st[x*2+2] = st[x];
}
st[x] = -1;
}
if (~st2[x]) {
sum2[x] = mul(r-l+1, st2[x]);
if (l != r) {
st2[x*2+1] = st2[x*2+2] = st2[x];
}
st2[x] = -1;
}
}
ll get2(int li, int ri, int x, int l, int r) {
prop2(li, ri, x);
if (li >= l && ri <= r)return sum[x];
if (li > r || ri < l)return 0;
int m = (li + ri) >> 1;
return add(get2(li, m, x*2+1, l, r), get2(m+1, ri, x*2+2, l, r));
}
void upd2(int li, int ri, int x, int l, int r, ll val) {
prop2(li, ri, x);
if (li >= l && ri <= r) {
//cout << li << " " << ri << " " << sum[x] << " " << sum2[x] << " ";
st[x] = val;
tak[x] = true;
tak2[x] = false;
prop2(li, ri, x);
//cout << sum[x] << " " << sum2[x] << " " << val << "\n";
return;
}
if (li > r || ri < l)return;
int m = (li + ri) >> 1;
upd2(li, m, x*2+1, l, r, val);
upd2(m+1, ri, x*2+2, l, r, val);
sum[x] = add(sum[x*2+1], sum[x*2+2]);
}
void upd3(int li, int ri, int x, int l, int r, ll val) {
prop2(li, ri, x);
if (li >= l && ri <= r) {
st2[x] = val;
tak2[x] = false;
prop2(li, ri, x);
return;
}
if (li > r || ri < l)return;
int m = (li + ri) >> 1;
upd3(li, m, x*2+1, l, r, val);
upd3(m+1, ri, x*2+2, l, r, val);
sum2[x] = add(sum2[x*2+1], sum2[x*2+2]);
}
void hld_init(int u) {
in2[u] = id++;
if (adj[u].empty())return;
int hc, mx = 0;
for (auto &v : adj[u]) {
if (sz[v] > mx) {
mx = sz[v];
hc = v;
}
}
fr[hc] = fr[u];
hld_init(hc);
for (auto &v : adj[u]) {
if (v == hc)continue;
fr[v] = v;
hld_init(v);
}
}
void hld_upd(int u, int v, ll val) {
val %= M;
//cout << "ace " << u << " " << v<< "\n";
while (fr[u] != fr[v]) {
if (in2[u] < in2[v])swap(u, v);
upd2(0, n-1, 0, in2[fr[u]], in2[u], val);
u = p[fr[u]][0];
}
upd2(0, n-1, 0, min(in2[u], in2[v]), max(in2[u], in2[v]), val);
}
void hld_upd2(int u, int v, ll val) {
val %= M;
while (fr[u] != fr[v]) {
if (in2[u] < in2[v])swap(u, v);
upd3(0, n-1, 0, in2[fr[u]], in2[u], val);
u = p[fr[u]][0];
}
upd3(0, n-1, 0, min(in2[u], in2[v]), max(in2[u], in2[v]), val);
}
void build(int l, int r, int x) {
if (l == r) {
mx[x].S = rin[l];
return;
}
int m = (l + r) >> 1;
build(l, m, x*2+1);
build(m+1, r, x*2+2);
}
int main () {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 0; i < (1 << 18); i++) {
st[i] = st2[i] = -1;
}
for (int i = 1; i < n; i++) {
int par;
cin >> par;
adj[par].pb(i);
}
init(0);
build(0, n-1, 0);
id = 0;
hld_init(0);
for (int i = 1; i < n; i++) {
int u = i;
ll ad;
cin >> ad;
int anc = u;
ll maxi = get(0, n-1, 0, in[u], in[u]+sz[u]-1).F;
for (int i = 17; i >= 0; i--) {
if (get(0, n-1, 0, in[p[anc][i]], in[p[anc][i]] + sz[p[anc][i]]-1).F < ad+maxi) {
anc = p[anc][i];
}
}
if (anc != u)hld_upd(p[u][0], anc, maxi+ad);
int tmp = anc;
for (int i = 17; i >= 0; i--) {
pair<ll, ll> xx = get(0, n-1, 0, in[p[anc][i]], in[p[anc][i]] + sz[p[anc][i]]-1);
int xi = pr(xx.S, p[anc][i]);
ll val = max(get(0, n-1, 0, in[p[anc][i]], in[xi]-1).F, get(0, n-1, 0, in[xi]+1, in[p[anc][i]] + sz[p[anc][i]]-1).F);
if (val < ad+maxi) {
anc = p[anc][i];
}
}
if (anc != tmp)hld_upd2(p[tmp][0], anc, maxi+ad);
upd(0, n-1, 0, in[u], in[u]+sz[u]-1, ad);
}
cout << sub(add(sum[0], sum2[0]), sd) << "\n";
int q;
cin >> q;
for (int i = 0; i < q; i++) {
int u;
ll ad;
cin >> u >> ad;
int anc = u;
ll maxi = get(0, n-1, 0, in[u], in[u]+sz[u]-1).F;
for (int i = 17; i >= 0; i--) {
if (get(0, n-1, 0, in[p[anc][i]], in[p[anc][i]] + sz[p[anc][i]]-1).F < ad+maxi) {
anc = p[anc][i];
}
}
if (anc != u)hld_upd(p[u][0], anc, maxi+ad);
int tmp = anc;
for (int i = 17; i >= 0 && anc; i--) {
pair<ll, ll> xx = get(0, n-1, 0, in[p[anc][i]], in[p[anc][i]] + sz[p[anc][i]]-1);
int xi = pr(p[anc][i], xx.S);
ll val = max(get(0, n-1, 0, in[p[anc][i]], in[xi]-1).F, get(0, n-1, 0, in[xi]+sz[xi], in[p[anc][i]] + sz[p[anc][i]]-1).F);
//if (!i)cout << xx.F << " " << xx.S << " " << xi << " " << val << "\n";
if (val < ad+maxi) {
anc = p[anc][i];
}
}
if (anc != tmp)hld_upd2(p[tmp][0], anc, maxi+ad);
ll xxx = get(0, n-1, 0, in[u], in[u]).F;
sd = (sd + xxx) % M;
upd(0, n-1, 0, in[u], in[u]+sz[u]-1, ad);
cout << sub(add(sum2[0], sum[0]), sd) << "\n";
}
}
Compilation message
arboras.cpp: In function 'void hld_init(int)':
arboras.cpp:172:3: warning: 'hc' may be used uninitialized in this function [-Wmaybe-uninitialized]
172 | if (v == hc)continue;
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
18996 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5052 ms |
34916 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5033 ms |
21788 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
13 ms |
18996 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
