#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define REB(i,m,n) for(int i=(m); i>=(n); i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define MP make_pair
#define fs first
#define se second
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define pb push_back
#define SZ(v) (ll)v.size()
#define ALL(v) v.begin(),v.end()
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count());
ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); }
const int N = 2e5 + 7;
const int Mod = 1e9 + 7;///lon
const int INF = 2e9 + 7;
const int BASE = 137;
const int szBL = 320;
inline void Sub (ll &A, ll B) {
A -= B;
A %= Mod;
if (A < 0) A += Mod;
}
inline void Add (ll &A, ll B) {
A += B;
A %= Mod;
}
#define Gmultiset multiset<ll, greater<ll>>
int n, m, Q;
int a[N];
int P[N], D[N];
vector<pll> ke[N];
Gmultiset S[N];
int szC[N];
int tin[N], tout[N], Head[N], pa[N], par[N][25];
struct Segment_Tree_Dist {
int m;
ll st[N << 2], lz[N << 2], sum[N << 2];
void init (int n) {
m = n;
}
void down (int id, int l, int r) {
int mid = l + r >> 1;
(sum[id << 1] += lz[id] * (mid - l + 1) % Mod) %= Mod;
(sum[id << 1 | 1] += lz[id] * (r - mid) % Mod) %= Mod;
rep (i, id << 1, id << 1 | 1) {
st[i] += lz[id];
lz[i] += lz[id];
}
lz[id] = 0;
}
void update (int id, int l, int r, int u, int v, ll val) {
if (l > v || r < u) return;
if (l >= u && r <= v) {
st[id] += val;
lz[id] += val;
(sum[id] += val * (r - l + 1) % Mod) %= Mod;
return;
}
int mid = l + r >> 1;
down(id, l, r);
update (id << 1, l, mid, u, v, val);
update (id << 1 | 1, mid + 1, r, u, v, val);
st[id] = max(st[id << 1], st[id << 1 | 1]);
sum[id] = (sum[id << 1] + sum[id << 1 | 1]) % Mod;
}
ll get (int id, int l, int r, int u, int v) {
if (l > v || r < u || u > v) return 0;
if (l >= u && r <= v) return st[id];
int mid = l + r >> 1;
down(id, l, r);
return max(get(id << 1, l, mid, u, v), get (id << 1 | 1, mid + 1, r, u, v));
}
void update (int u, int v, ll val) {
update (1, 1, m, u, v, val);
}
ll getS (int id, int l, int r, int u, int v) {
if (l > v || r < u) return 0;
if (l >= u && r <= v) return sum[id];
int mid = l + r >> 1;
down(id, l, r);
return max(get(id << 1, l, mid, u, v), get (id << 1 | 1, mid + 1, r, u, v));
}
ll get (int u, int v) {
return get (1, 1, m, u, v);
}
ll getS (int u, int v) {
return getS (1, 1, m, u, v);
}
}ST;
struct Segment_Tree_Max2 {
ll st[N << 2], lz[N << 2], lz2[N << 2];
void init (int n) {
m = n;
rep (i, 1, n << 2) lz[i] = -1;
}
void down (int id, int l, int r) {
int mid = l + r >> 1;
if (lz[id] != -1) {
st[id << 1] = lz[id] * (mid - l + 1) % Mod;
lz[id << 1] = lz[id];
st[id << 1 | 1] = lz[id] * (r - mid) % Mod;
lz[id << 1 | 1] = lz[id];
}
else {
(st[id << 1] += lz2[id] * (mid - l + 1) % Mod) %= Mod;
(lz2[id << 1] += lz2[id]) %= Mod;
(st[id << 1 | 1] += lz2[id] * (r - mid) % Mod) %= Mod;
(lz2[id << 1 | 1] += lz2[id]) %= Mod;
}
lz[id] = -1;
lz2[id] = 0;
}
void update (int id, int l, int r, int u, int v, ll val) {
if (l > v || r < u || u > v) return;
if (l >= u && r <= v) {
st[id] = val * (r - l + 1) % Mod;
lz[id] = val;
return;
}
int mid = l + r >> 1;
down(id, l, r);
update (id << 1, l, mid, u, v, val);
update (id << 1 | 1, mid + 1, r, u, v, val);
st[id] = (st[id << 1] + st[id << 1 | 1]) % Mod;
}
void Add (int id, int l, int r, int u, int v, ll val) {
if (l > v || r < u || u > v) return;
if (l >= u && r <= v) {
(st[id] += val * (r - l + 1) % Mod) %= Mod;
if (lz[id] == -1) (lz2[id] += val) %= Mod;
else (lz[id] += val) %= Mod;
return;
}
int mid = l + r >> 1;
down(id, l, r);
Add (id << 1, l, mid, u, v, val);
Add (id << 1 | 1, mid + 1, r, u, v, val);
st[id] = (st[id << 1] + st[id << 1 | 1]) % Mod;
}
ll get (int id, int l, int r, int u, int v) {
if (l > v || r < u || u > v) return 0;
if (l >= u && r <= v) return st[id];
int mid = l + r >> 1;
down(id, l, r);
return max(get(id << 1, l, mid, u, v), get (id << 1 | 1, mid + 1, r, u, v));
}
void update (int u, int v, ll val) {
if (u == 0) return;
update (1, 1, m, u, v, val);
}
void Add (int u, int v, ll val) {
Add (1, 1, m, u, v, val);
}
ll get (int u, int v) {
return get (1, 1, m, u, v);
}
}ST2;
void process () {
cin >> n;
rep (i, 2, n) cin >> P[i], ++P[i];
// rep (i, 2, n) {
// cout << P[i] <<" "<<i<<"\n";
// }
rep (i, 2, n) cin >> D[i];
rep (i, 2, n) {
ke[P[i]].pb({i, D[i]});
}
function<void(int, int)> pdfs = [&] (int u, int p) {
szC[u] = 1;
par[u][0] = pa[u] = p;
rep (i, 1, 20) par[u][i] = par[par[u][i - 1]][i - 1];
iter (&id, ke[u]) {
int v = id.fs;
pdfs(v, u);
szC[u] += szC[v];
}
};
pdfs(1, 0);
vector<ll> dp(n + 3, 0), toP(n + 3, 0), bigC(n + 3, 0); ///update toP
ST.init(n), ST2.init(n);
auto comp = [&] (Gmultiset &cur, int mxV) -> ll {
ll s1 = (mxV == -1 ? 0 : dp[mxV] + toP[mxV]);
ll s2 = (SZ(cur) < 2 ? 0 : *next(cur.begin()));
return max(s1, s2);
};
auto FindMax = [&] (Gmultiset &cur) -> ll {
return cur.empty() ? 0 : *cur.begin();
};
ll res = 0;
function<void(int, int)> hld = [&] (int u, int p) {
static int time_dfs = 0;
tin[u] = ++time_dfs;
Head[u] = p;
int mxV = -1;
iter (&id, ke[u]) {
int v = id.fs, w = id.se;
toP[v] = w;
if (mxV == -1 || szC[v] > szC[mxV]) mxV = v;
}
bigC[u] = mxV;
if (mxV != -1)
hld(mxV, p);
iter (&id, ke[u]) {
int v = id.fs;
if (v == mxV) continue;
hld(v, v);
}
tout[u] = time_dfs;
ST.update (tin[u], tout[u], toP[u]);
iter (&id, ke[u]) {
int v = id.fs, w = id.se;
if (v != mxV) S[u].insert(dp[v] + w);
dp[u] = max(dp[u], dp[v] + w);
}
// cout << u <<": \n";
// iter (&id, S[u]) cout << id <<" ";
// cout <<"\n";
ll preVal = ST.get(tin[u], tout[u]);
ST2.update(tin[u], tin[u], (comp(S[u], bigC[u]) + preVal) % Mod);
Add(res, FindMax(S[u]));
};
hld(1, 1);
cout << ((res + ST2.st[1]) % Mod - ST.sum[1] + Mod) % Mod<<"\n";
auto Erase = [&] (Gmultiset &cur, ll W) -> void {
assert(cur.find(W) != cur.end());
cur.erase(cur.find(W));
};
///if them chain[u] != chain[pa]
auto Upd = [&] (int X, int Val) {
ST.update (tin[X], tout[X], Val);
ST2.Add(tin[X], tout[X], Val);
auto Find = [&] (int u, ll maxx) {
if (ST.get(tin[u], tout[u]) > maxx) return u;
REB (i, 20, 0) {
int cur = par[u][i];
if (ST.get(tin[cur], tout[cur]) <= maxx) {
u = cur;
}
}
return pa[u];
};
int cur = X;
ll maxx = ST.get(tin[X], tout[X]);
int pmax = Find(pa[cur], maxx);
// cout << X << ": "<<pmax <<"\n";
auto getMx = [&] (Gmultiset &cur, ll bigV) {
ll s2 = (SZ(cur) < 2 ? 0 : *next(cur.begin()));
return max(s2, bigV);
};
auto trans_phase = [&] (int u, ll maxx) {
int ver = pa[u];
if (ver == 0) return;
assert(!S[ver].empty());
assert(bigC[ver] != -1);
Sub(res, FindMax(S[ver]));
Erase(S[ver], dp[u] + toP[u]);
dp[u] = ST.get(tin[u], tout[u]) - ST.get(tin[u], tin[u]);
if (u == X) toP[u] += Val;
S[ver].insert(dp[u] + toP[u]);
// if (X == 5 && Val == 2) {
// cout <<"hihihihih: "<<dp[u] <<" "<<toP[u] <<"\n";
// iter (&id, S[ver]) cout << id <<" ";
// cout <<"\n";
// }
// cout << "hihi: "<<ver<<" "<<res<<" "<<FindMax(S[ver])<<"\n";
Add(res, FindMax(S[ver]));
ll preVal = ST.get(tin[ver], tin[ver]);
ll dpbigC = ST.get(tin[bigC[ver]], tin[bigC[ver]]);
ST2.update(tin[ver], tin[ver], (getMx(S[ver], dpbigC - preVal) % Mod + preVal) % Mod);
};
while (Head[cur] != Head[pmax]) {
ST2.update(tin[Head[cur]], tin[pa[cur]], maxx);
trans_phase(Head[cur], maxx);
cur = pa[Head[cur]];
}
ST2.update(tin[pmax] + 1, tin[pa[cur]], maxx);
ll preVal = ST.get(tin[pmax], tin[pmax]);
assert(bigC[pmax] != -1);
ll dpbigC = ST.get(tin[bigC[pmax]], tout[bigC[pmax]]);
// cout << X<<" "<<pmax <<" "<<bigC[pmax]<<" "<<dpbigC<<" asdasasddfff\n";
ST2.update(tin[pmax], tin[pmax], (getMx(S[pmax], dpbigC - preVal) % Mod + preVal) % Mod); ///ko co chuyen pmax la duoi cua 1 chain
};
cin >> Q;
rep (q, 1, Q) {
ll u, val;
cin >> u >> val;
++u;
Upd(u, val);
// cout << u <<" "<<val<<" asdasd:\n";
// rep (i, 1, n) cout << ST2.get(tin[i], tin[i]) <<" ";
// cout <<"\n";
// cout << res<<" "<<ST2.st[1]<<" "<< ST.sum[1]<<" "<<((res + ST2.st[1]) % Mod - ST.sum[1] % Mod + Mod) % Mod <<" aa\n";
cout << ((res + ST2.st[1]) % Mod - ST.sum[1] % Mod + Mod) % Mod<<"\n";
}
}
#define file(name) if(fopen(name".inp","r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
main () {
// file("c");
ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
int num_Test = 1;
// cin >> num_Test;
while (num_Test--) {
process();
}
}
/*
onepunch +27
5
0 0 1 1
0 0 0 0
8
1 2
2 2
3 2
4 2
4 1
3 1
2 1
1 1
*/
Compilation message
arboras.cpp: In member function 'void Segment_Tree_Dist::down(int, int, int)':
arboras.cpp:57:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
57 | int mid = l + r >> 1;
| ~~^~~
arboras.cpp: In member function 'void Segment_Tree_Dist::update(int, int, int, int, int, long long int)':
arboras.cpp:74:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
74 | int mid = l + r >> 1;
| ~~^~~
arboras.cpp: In member function 'long long int Segment_Tree_Dist::get(int, int, int, int, int)':
arboras.cpp:84:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
84 | int mid = l + r >> 1;
| ~~^~~
arboras.cpp: In member function 'long long int Segment_Tree_Dist::getS(int, int, int, int, int)':
arboras.cpp:94:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
94 | int mid = l + r >> 1;
| ~~^~~
arboras.cpp: In member function 'void Segment_Tree_Max2::down(int, int, int)':
arboras.cpp:114:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
114 | int mid = l + r >> 1;
| ~~^~~
arboras.cpp: In member function 'void Segment_Tree_Max2::update(int, int, int, int, int, long long int)':
arboras.cpp:137:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
137 | int mid = l + r >> 1;
| ~~^~~
arboras.cpp: In member function 'void Segment_Tree_Max2::Add(int, int, int, int, int, long long int)':
arboras.cpp:151:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
151 | int mid = l + r >> 1;
| ~~^~~
arboras.cpp: In member function 'long long int Segment_Tree_Max2::get(int, int, int, int, int)':
arboras.cpp:160:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
160 | int mid = l + r >> 1;
| ~~^~~
arboras.cpp: At global scope:
arboras.cpp:320:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
320 | main () {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
29264 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
908 ms |
64072 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
649 ms |
67144 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
29264 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
