#include <bits/stdc++.h>
using namespace std;
constexpr int MOD = 1e9 + 7;
constexpr int NMAX = 1e5 + 5;
typedef long long LL;
typedef pair <LL, int> PLI;
int Root = 0;
vector <int> G[NMAX];
int N;
int Dad[NMAX];
LL Cost[NMAX];
int Level[NMAX];
int Size[NMAX];
int poz[NMAX];
int prec[NMAX];
int Euler[NMAX];
PLI arb[4*NMAX];
LL Lazy[4*NMAX];
void Propag (int Node, int a, int b) {
if (Lazy[Node] == 0) return;
if (a == b) return;
arb[2*Node].first += Lazy[Node];
arb[2*Node+1].first += Lazy[Node];
Lazy[2*Node] += Lazy[Node];
Lazy[2*Node+1] += Lazy[Node];
Lazy[Node] = 0;
}
void Initialize (int Node, int a, int b, int pos, LL val) {
if (a == b) {
arb[Node] = {val, Euler[a]};
return;
}
int mij = (a + b) / 2;
if (pos <= mij) Initialize(2*Node, a, mij, pos, val);
else Initialize(2*Node+1, mij+1, b, pos, val);
arb[Node] = max(arb[2*Node], arb[2*Node+1]);
}
void Update (int Node, int a, int b, int ua, int ub, LL val) {
if (ua <= a && b <= ub) {
Lazy[Node] += val;
arb[Node].first += val;
return;
}
Propag(Node, a, b);
int mij = (a + b) / 2;
if (ua <= mij) Update(2*Node, a, mij, ua, ub, val);
if (mij < ub) Update(2*Node+1, mij+1, b, ua, ub, val);
arb[Node] = max(arb[2*Node], arb[2*Node+1]);
}
PLI Query (int Node, int a, int b, int qa, int qb) {
Propag(Node, a, b);
if (qa > qb) return {0, -1};
if (qa <= a && b <= qb) return arb[Node];
int mij = (a + b) / 2;
PLI Left = {0, -1}, Right = {0, -1};
if (qa <= mij) Left = Query(2*Node, a, mij, qa, qb);
if (mij < qb) Right = Query(2*Node+1, mij+1, b, qa, qb);
return max(Left, Right);
}
PLI Maximum (int Node) {
return Query(1, 1, N, poz[Node], poz[Node] + Size[Node] - 1);
}
PLI SecondMaximum (int Node) {
PLI M = Maximum(Node);
if (G[Node].size() <= 1) return Query(1, 1, N, poz[Node], poz[Node]);
int st = 0, dr = G[Node].size()-1;
int ans = 0;
while (st <= dr) {
int mij = (st + dr) / 2;
if (poz[G[Node][mij]] <= poz[M.second]){
ans = mij;
st = mij + 1;
}
else dr = mij - 1;
}
ans = G[Node][ans];
return max(Query(1, 1, N, poz[Node], poz[ans]-1), Query(1, 1, N, poz[ans] + Size[ans], poz[Node] + Size[Node] - 1));
}
int aux = 0;
void Dfs (int Node) {
Size[Node] = 1;
Euler[++aux] = Node;
poz[Node] = aux;
for (auto it : G[Node]) {
Cost[it] += Cost[Node];
Level[it] = Level[Node] + 1;
Dfs(it);
Size[Node] += Size[it];
}
}
void Read () {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N;
for (int i = 1; i < N; ++ i ) {
cin >> Dad[i];
G[Dad[i]].push_back(i);
}
for (int i = 1; i < N; ++ i )
cin >> Cost[i];
Dfs(Root);
}
LL Sum_Total;
LL Sum_Maxim;
LL Sum_Second;
void Precalculare () {
for (int i = 0; i < N; ++ i )
Initialize(1, 1, N, poz[i], Cost[i]);
///Max + Second - 2 * LCA
for (int i = 0; i < N; ++ i )
prec[i] = i;
for (int i = 0; i < N; ++ i ) {
PLI x = Maximum(i);
PLI y = SecondMaximum(i);
Sum_Maxim += x.first;
Sum_Second += y.first;
Sum_Total += Cost[i];
if (Level[prec[x.second]] > Level[i]) prec[x.second] = i;
}
cout << (Sum_Maxim + Sum_Second - 2 * Sum_Total) % MOD << '\n';
}
void Solve () {
int Q;
cin >> Q;
for (; Q; -- Q ) {
int node;
LL v;
cin >> node >> v;
Sum_Total += 1LL * Size[node] * v;
Sum_Maxim += 1LL * Size[node] * v;
Sum_Second += 1LL * Size[node] * v;
PLI val = Query(1, 1, N, poz[node], poz[node] + Size[node] - 1);
val.first += v;
Sum_Maxim += (Level[node] - Level[prec[val.second]]) * v;
int curr = prec[val.second];
while (curr > 0) {
PLI Best_Dad_Path = Maximum(Dad[curr]);
if (Best_Dad_Path > val) {
PLI Second_Dad_Path = SecondMaximum(Dad[curr]);
if (Second_Dad_Path < val) Sum_Second += (val.first - Second_Dad_Path.first);
break;
}
PLI Second_Dad_Path = SecondMaximum(Dad[curr]);
Sum_Second += Best_Dad_Path.first - Second_Dad_Path.first;
int urm = prec[Best_Dad_Path.second];
Sum_Maxim += (Level[curr] - Level[urm]) * (val.first - Best_Dad_Path.first);
int Node = Dad[curr];
int st = 0, dr = G[Node].size()-1;
int ans = -1;
while (st <= dr) {
int mij = (st + dr) / 2;
if (poz[G[Node][mij]] <= poz[Best_Dad_Path.second]){
ans = mij;
st = mij + 1;
}
else dr = mij - 1;
}
ans = G[Node][ans];
prec[Best_Dad_Path.second] = ans;
prec[val.second] = urm;
curr = urm;
}
cout << (Sum_Maxim + Sum_Second - 2 * Sum_Total) % MOD << '\n';
Update(1, 1, N, poz[node], poz[node]+Size[node]-1, v);
}
}
int main () {
Read();
Precalculare();
Solve();
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2764 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2764 KB |
Output is correct |
| 3 |
Correct |
3 ms |
2808 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
357 ms |
15348 KB |
Output is correct |
| 2 |
Correct |
213 ms |
15044 KB |
Output is correct |
| 3 |
Correct |
273 ms |
15224 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
329 ms |
16324 KB |
Output is correct |
| 2 |
Correct |
196 ms |
21044 KB |
Output is correct |
| 3 |
Correct |
346 ms |
16636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
2764 KB |
Output is correct |
| 2 |
Correct |
3 ms |
2764 KB |
Output is correct |
| 3 |
Correct |
3 ms |
2808 KB |
Output is correct |
| 4 |
Correct |
357 ms |
15348 KB |
Output is correct |
| 5 |
Correct |
213 ms |
15044 KB |
Output is correct |
| 6 |
Correct |
273 ms |
15224 KB |
Output is correct |
| 7 |
Correct |
329 ms |
16324 KB |
Output is correct |
| 8 |
Correct |
196 ms |
21044 KB |
Output is correct |
| 9 |
Correct |
346 ms |
16636 KB |
Output is correct |
| 10 |
Correct |
343 ms |
18396 KB |
Output is correct |
| 11 |
Correct |
209 ms |
20872 KB |
Output is correct |
| 12 |
Correct |
293 ms |
16476 KB |
Output is correct |
| 13 |
Correct |
211 ms |
18920 KB |
Output is correct |
| 14 |
Correct |
179 ms |
19612 KB |
Output is correct |
