#include <stdio.h>
#include <stdlib.h>
#define N 100000
#define N_ (1 << 17) /* N_ = pow2(ceil(log2(N + 1))) */
#define MD 1000000007
long long max(long long a, long long b) { return a > b ? a : b; }
int *ej[N], eo[N], n;
void append(int i, int j) {
int o = eo[i]++;
if (o >= 2 && (o & o - 1) == 0)
ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
ej[i][o] = j;
}
int dd[N], pp[N], qq[N], jj[N], jj1[N], jj2[N], ta[N], tb[N], qu[N], ww[N]; long long dp[N];
int dfs1(int p, int i, int d) {
int o, s, k_, j_, j1, j2;
dd[i] = d, pp[i] = p;
s = 1, k_ = 0, j_ = -1, j1 = -1, j2 = -1;
for (o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != p) {
int k = dfs1(i, j, d + 1);
s += k;
if (k_ < k)
k_ = k, j_ = j;
dp[j] += ww[j];
if (j1 == -1 || dp[j1] < dp[j])
j2 = j1, j1 = j;
else if (j2 == -1 || dp[j2] < dp[j])
j2 = j;
}
}
jj[i] = j_;
dp[i] = j1 == -1 ? 0 : dp[j1], jj1[i] = j1, jj2[i] = j2;
return s;
}
long long st[N_ * 2], lz[N_]; int h_, n_;
void put(int i, long long x) {
st[i] += x;
if (i < n_)
lz[i] += x;
}
void pus(int i) {
if (lz[i])
put(i << 1 | 0, lz[i]), put(i << 1 | 1, lz[i]), lz[i] = 0;
}
void pul(int i) {
if (!lz[i])
st[i] = max(st[i << 1 | 0], st[i << 1 | 1]);
}
void push(int i) {
int h;
for (h = h_; h > 0; h--)
pus(i >> h);
}
void pull(int i) {
while (i > 1)
pul(i >>= 1);
}
void build() {
static long long dd[N + 1];
int i;
for (i = 1; i < n; i++)
dd[ta[i]] += ww[i], dd[tb[i]] -= ww[i];
for (i = 1; i < n; i++)
dd[i] += dd[i - 1];
for (i = 0; i < n_; i++)
st[n_ + i] = i < n ? dd[i] : 0;
for (i = n_ - 1; i > 0; i--)
pul(i);
}
void update(int l, int r, int x) {
int l_ = l += n_, r_ = r += n_;
push(l_), push(r_);
for ( ; l <= r; l >>= 1, r >>= 1) {
if ((l & 1) == 1)
put(l++, x);
if ((r & 1) == 0)
put(r--, x);
}
pull(l_), pull(r_);
}
long long query(int l, int r) {
long long x;
push(l += n_), push(r += n_);
x = 0;
for ( ; l <= r; l >>= 1, r >>= 1) {
if ((l & 1) == 1)
x = max(x, st[l++]);
if ((r & 1) == 0)
x = max(x, st[r--]);
}
return x;
}
int st_[N_ * 2];
void pul_(int i) {
st_[i] = st_[i << 1 | 0] && st_[i << 1 | 1];
}
void update_(int i, int x) {
st_[i += n_] = x;
while (i > 1)
pul_(i >>= 1);
}
int query_(int r) {
int l = 0;
for (l += n_, r += n_; l <= r; l >>= 1, r >>= 1)
if ((r & 1) == 0) {
if (!st_[r]) {
while (r < n_)
r = !st_[r << 1 | 1] ? r << 1 | 1 : r << 1 | 0;
return r - n_;
}
r--;
}
return -1;
}
void dfs2(int p, int i, int q) {
static int time;
int o, j_;
qu[ta[i] = time++] = i;
qq[i] = q;
j_ = jj[i];
if (j_ != -1) {
dfs2(i, j_, q);
update_(ta[j_], j_ == jj1[i]);
}
for (o = eo[i]; o--; ) {
int j = ej[i][o];
if (j != p && j != j_)
dfs2(i, j, j);
}
tb[i] = time;
}
int main() {
int q, i, j, w, sum;
scanf("%d", &n);
for (i = 0; i < n; i++)
ej[i] = (int *) malloc(2 * sizeof *ej[i]);
for (j = 1; j < n; j++) {
scanf("%d", &pp[j]);
append(pp[j], j);
}
for (j = 1; j < n; j++)
scanf("%d", &ww[j]);
dfs1(-1, 0, 0);
while (1 << h_ <= n)
h_++;
n_ = 1 << h_;
dfs2(-1, 0, 0);
build();
sum = 0;
for (i = 0; i < n; i++)
sum = (sum + (jj1[i] == -1 ? 0 : dp[jj1[i]]) + (jj2[i] == -1 ? 0 : dp[jj2[i]])) % MD;
scanf("%d", &q);
printf("%d\n", sum);
while (q--) {
int x;
long long d, d1, d2;
scanf("%d%d", &j, &w);
update(ta[j], tb[j] - 1, w);
ww[j] += w, x = w;
while (1) {
i = qu[query_(ta[j])];
sum = (sum + (long long) x * (dd[j] - dd[i])) % MD;
j = i;
if (j == 0)
break;
i = pp[j];
if (jj1[i] == j)
sum = (sum + x) % MD;
else {
d = query(ta[j], tb[j] - 1);
d1 = query(ta[jj1[i]], tb[jj1[i]] - 1);
d2 = query(ta[jj2[i]], tb[jj2[i]] - 1);
if (d1 < d) {
sum = (sum + (j == jj2[i] ? x : d - d2)) % MD;
x = d - d1;
jj2[i] = jj1[i], jj1[i] = j;
update_(ta[jj[i]], jj[i] == j);
} else {
if (jj2[i] == j)
sum = (sum + x) % MD;
else if (d2 < d) {
sum = (sum + d - d2) % MD;
jj2[i] = j;
}
break;
}
}
j = i;
}
if (sum < 0)
sum += MD;
printf("%d\n", sum);
}
return 0;
}
Compilation message
arboras.c: In function 'append':
arboras.c:15:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
15 | if (o >= 2 && (o & o - 1) == 0)
| ~~^~~
arboras.c: In function 'main':
arboras.c:169:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
169 | scanf("%d", &n);
| ^~~~~~~~~~~~~~~
arboras.c:173:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
173 | scanf("%d", &pp[j]);
| ^~~~~~~~~~~~~~~~~~~
arboras.c:177:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
177 | scanf("%d", &ww[j]);
| ^~~~~~~~~~~~~~~~~~~
arboras.c:187:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
187 | scanf("%d", &q);
| ^~~~~~~~~~~~~~~
arboras.c:193:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
193 | scanf("%d%d", &j, &w);
| ^~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
111 ms |
14816 KB |
Output is correct |
| 2 |
Correct |
67 ms |
15692 KB |
Output is correct |
| 3 |
Correct |
83 ms |
15836 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
103 ms |
16396 KB |
Output is correct |
| 2 |
Correct |
92 ms |
21464 KB |
Output is correct |
| 3 |
Correct |
107 ms |
17328 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
468 KB |
Output is correct |
| 2 |
Correct |
1 ms |
468 KB |
Output is correct |
| 3 |
Correct |
1 ms |
468 KB |
Output is correct |
| 4 |
Correct |
111 ms |
14816 KB |
Output is correct |
| 5 |
Correct |
67 ms |
15692 KB |
Output is correct |
| 6 |
Correct |
83 ms |
15836 KB |
Output is correct |
| 7 |
Correct |
103 ms |
16396 KB |
Output is correct |
| 8 |
Correct |
92 ms |
21464 KB |
Output is correct |
| 9 |
Correct |
107 ms |
17328 KB |
Output is correct |
| 10 |
Correct |
105 ms |
18484 KB |
Output is correct |
| 11 |
Correct |
84 ms |
21196 KB |
Output is correct |
| 12 |
Correct |
95 ms |
17128 KB |
Output is correct |
| 13 |
Correct |
85 ms |
19404 KB |
Output is correct |
| 14 |
Correct |
85 ms |
20136 KB |
Output is correct |
