/**
____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|
**/
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 1e5 + 10;
const ll mod = 1e9 + 7;
int n, q;
int heavy[maxn], ch_idx[maxn], ch_pos[maxn], ch_head[maxn];
int par[maxn], depth[maxn], sub[maxn], strong[maxn];
ll dp[maxn][2], dis[maxn];
vector < pair < int, ll > > g[maxn];
void dfs(int v)
{
heavy[v] = -1;
strong[v] = -1;
for (pair < int, ll > nb : g[v])
{
if (nb.first == par[v])
continue;
depth[nb.first] = depth[v] + 1;
dfs(nb.first);
if (heavy[v] == -1 || sub[nb.first] > sub[heavy[v]])
heavy[v] = nb.first;
if (dp[nb.first][0] + nb.second >= dp[v][0])
{
dp[v][1] = dp[v][0];
dp[v][0] = dp[nb.first][0] + nb.second;
strong[v] = nb.first;
}
else if (dp[nb.first][0] + nb.second > dp[v][1])
{
dp[v][1] = dp[nb.first][0] + nb.second;
}
}
}
const int block = 20;
ll ans = 0;
pair < ll, ll > tree[4 * maxn];
ll lazy[4 * maxn], nxt_free, pot[maxn];
struct chain
{
vector < int > ver;
vector < pair < ll, ll > > st;
set < int > weak;
int ch_root;
void build_tree(int root, int left, int right)
{
if (left == right)
{
pot[ver[left]] = ch_root + root;
tree[ch_root + root] = st[left];
return;
}
int mid = (left + right) / 2;
build_tree(root * 2, left, mid);
build_tree(root * 2 + 1, mid + 1, right);
}
void build_chain()
{
for (int i = 0; i < ver.size(); i ++)
{
st.push_back({dp[ver[i]][0], dp[ver[i]][1]});
if (i != (int)(ver.size()) - 1)
{
if (strong[ver[i]] != ver[i + 1])
weak.insert(i);
}
}
ch_root = nxt_free;
nxt_free += ver.size() * 4;
build_tree(1, 0, (int)st.size() - 1);
}
void push_lazy(int root, int left, int right)
{
///if (lazy[root].first == lazy[root].second && lazy[root].first == 0)
if (left == right)
{
tree[root + ch_root].first += lazy[ch_root + root];
}
else
{
lazy[ch_root + root * 2] += lazy[ch_root + root];
lazy[ch_root + root * 2 + 1] += lazy[ch_root + root];
}
lazy[ch_root + root] = 0;
}
pair < ll, ll > get_node(int root, int left, int right, int idx)
{
int mid;
while(true)
{
if (lazy[ch_root + root] != 0)
push_lazy(root, left, right);
if (left == right)
{
return tree[ch_root + root];
}
mid = (left + right) / 2;
if (idx <= mid)
{
root = root * 2;
right = mid;
}
else
{
root = root * 2 + 1;
left = mid + 1;
}
}
/**if (lazy[ch_root + root] != 0)
push_lazy(root, left, right);
if (left == right)
return tree[ch_root + root];
int mid = (left + right) / 2;
if (idx <= mid)
return get_node(root * 2, left, mid, idx);
return get_node(root * 2 + 1, mid + 1, right, idx);*/
}
void set_node(int root, int left, int right, int idx, pair < ll,ll > val)
{
int mid;
while(true)
{
if (lazy[ch_root + root] != 0)
push_lazy(root, left, right);
if (left == right)
{
tree[ch_root + root] = val;
return;
}
mid = (left + right) / 2;
if (idx <= mid)
{
root = root * 2;
right = mid;
}
else
{
root = root * 2 + 1;
left = mid + 1;
}
}
/**if (lazy[ch_root + root] != 0)
push_lazy(root, left, right);
if (left == right)
{
tree[ch_root + root] = val;
return;
}
int mid = (left + right) / 2;
if (idx <= mid)
set_node(root * 2, left, mid, idx, val);
else
set_node(root * 2 + 1, mid + 1, right, idx, val);*/
}
struct sol
{
int root, left, right, qleft, qright;
ll val;
sol(int _root, int _left, int _right, int _qleft, int _qright, ll _val)
{
root = _root;
left = _left;
right = _right;
qleft = _qleft;
qright = _qright;
val = _val;
}
};
void update_range(int root, int left, int right, int qleft, int qright, ll val)
{
if (lazy[ch_root + root] != 0)
push_lazy(root, left, right);
if (left == qleft && right == qright)
{
lazy[ch_root + root] = val;
push_lazy(root, left, right);
return;
}
int mid = (left + right) / 2;
if (qright <= mid)
update_range(root * 2, left, mid, qleft, qright, val);
else if (qleft > mid)
update_range(root * 2 + 1, mid + 1, right, qleft, qright, val);
else
{
update_range(root * 2, left, mid, qleft, mid, val);
update_range(root * 2 + 1, mid + 1, right, mid + 1, qright, val);
}
/**if (left > qright || right < qleft)
return;
if (left >= qleft && right <= qright)
{
lazy[root + ch_root] = val;
push_lazy(root, left, right);
return;
}
int mid = (left + right) / 2;
update_range(root * 2, left, mid, qleft, qright, val);
update_range(root * 2 + 1, mid + 1, right, qleft, qright, val);*/
}
pair < ll, ll > get_element(int v)
{
if (ver.size() < block)
return {dp[v][0], dp[v][1]};
return get_node(1, 0, (int)(ver.size()) - 1, ch_pos[v]);
}
void set_element(int v, pair < ll, ll > val)
{
if (ver.size() < block)
{
dp[v][0] = val.first;
dp[v][1] = val.second;
return;
}
set_node(1, 0, (int)(ver.size()) - 1, ch_pos[v], val);
}
void update_path(int lf, int rf, ll val)
{
if (ver.size() < block)
{
for (int i = lf; i <= rf; i ++)
dp[ver[i]][0] += val;
}
update_range(1, 0, (int)(ver.size()) - 1, lf, rf, val);
}
};
vector < chain > ch;
void hld(int v)
{
ch_pos[v] = ch.back().ver.size();
ch.back().ver.push_back(v);
ch_head[v] = ch.back().ver[0];
ch_idx[v] = (int)(ch.size()) - 1;
if (heavy[v] != -1)
{
hld(heavy[v]);
}
for (pair < int, ll > nb : g[v])
{
if (nb.first == par[v] || nb.first == heavy[v])
continue;
ch.emplace_back();
hld(nb.first);
}
}
void update(int v, ll d)
{
ll cur = dp[v][0];
dis[v] += d;
while(true)
{
if (v == 0)
break;
cur = cur + dis[v];
///cout << v << " :: " << cur << endl;
if (strong[par[v]] == v)
{
ans = ans + cur - dp[par[v]][0];
ans = (ans + mod) % mod;
dp[par[v]][0] = cur;
v = par[v];
continue;
}
if (cur <= dp[par[v]][1])
break;
if (cur <= dp[par[v]][0])
{
ans = ans + cur - dp[par[v]][1];
ans = (ans + mod) % mod;
dp[par[v]][1] = cur;
break;
}
ans = ans + cur - dp[par[v]][1];
ans = (ans + mod) % mod;
dp[par[v]][1] = dp[par[v]][0];
dp[par[v]][0] = cur;
strong[par[v]] = v;
v = par[v];
}
/**cout << "------------" << endl;
for (int i = 0; i < n; i ++)
cout << dp[i][0] << " " << dp[i][1] << endl;
cout << "------------" << endl;*/
}
void update_edge(int v, ll d)
{
dis[v] += d;
pair < ll, ll > cur, aft;
set < int > :: iterator it;
cur = ch[ch_idx[v]].get_element(v);
while(true)
{
///cout << "here " << v << endl;
if (v == 0)
break;
if (ch_head[v] == v)
{
///cur = ch[ch_idx[v]].get_element(v);
aft = ch[ch_idx[par[v]]].get_element(par[v]);
if (strong[par[v]] == v)
{
ans = (ans + cur.first + dis[v] - aft.first) % mod;
aft.first = cur.first + dis[v];
ch[ch_idx[par[v]]].set_element(par[v], aft);
v = par[v];
cur = aft;
}
else
{
if (cur.first + dis[v] <= aft.second)
break;
if (cur.first + dis[v] <= aft.first)
{
ans = (ans + cur.first + dis[v] - aft.second) % mod;
aft.second = cur.first + dis[v];
ch[ch_idx[par[v]]].set_element(par[v], aft);
break;
}
ans = (ans + cur.first + dis[v] - aft.second) % mod;
if (strong[par[v]] == ch[ch_idx[par[v]]].ver[ch_pos[par[v]] + 1])
ch[ch_idx[par[v]]].weak.insert(ch_pos[par[v]]);
strong[par[v]] = v;
aft.second = aft.first;
aft.first = cur.first + dis[v];
ch[ch_idx[par[v]]].set_element(par[v], aft);
v = par[v];
cur = aft;
continue;
}
}
else
{
int pos = 0;
if (!ch[ch_idx[v]].weak.empty())
{
it = ch[ch_idx[v]].weak.lower_bound(ch_pos[v]);
if (it != ch[ch_idx[v]].weak.begin())
{
it = prev(it);
pos = *it + 1;
}
}
/**for (int x : ch[ch_idx[v]].weak)
cout << x << " ";
cout << endl;*/
///cout << pos << " " << ch_pos[v] << endl;
if (pos == ch_pos[v])
{
///cur = ch[ch_idx[v]].get_element(v);
aft = ch[ch_idx[par[v]]].get_element(par[v]);
if (cur.first + dis[v] <= aft.second)
break;
if (cur.first + dis[v] <= aft.first)
{
ans = (ans + cur.first + dis[v] - aft.second) % mod;
aft.second = cur.first + dis[v];
ch[ch_idx[par[v]]].set_element(par[v], aft);
break;
}
strong[par[v]] = v;
ch[ch_idx[v]].weak.erase(pos - 1);
ans = (ans + cur.first + dis[v] - aft.second) % mod;
aft.second = aft.first;
aft.first = cur.first + dis[v];
ch[ch_idx[v]].set_element(par[v], aft);
v = par[v];
cur = aft;
continue;
}
else
{
///cur = ch[ch_idx[v]].get_element(v);
aft = ch[ch_idx[par[v]]].get_element(par[v]);
ll diff = cur.first + dis[v] - aft.first;
ans = (ans + diff * (ch_pos[v] - pos)) % mod;
ch[ch_idx[v]].update_path(pos, ch_pos[v] - 1, diff);
v = ch[ch_idx[v]].ver[pos];
cur = ch[ch_idx[v]].get_element(v);
continue;
}
}
}
}
void solve()
{
cin >> n;
for (int i = 1; i < n; i ++)
cin >> par[i];
for (int i = 1; i < n; i ++)
{
cin >> dis[i];
g[par[i]].push_back({i, dis[i]});
}
par[0] = -1;
dfs(0);
ch.emplace_back();
hld(0);
/**for (int i = 0; i < ch.size(); i ++)
{
cout << i << " : ";
for (int v : ch[i].ver)
cout << v << " ";
cout << endl;
}*/
for (int i = 0; i < ch.size(); i ++)
ch[i].build_chain();
for (int i = 0; i < ch.size(); i ++)
{
for (int j = 0; j < (int)ch[i].ver.size() - 1; j ++)
{
if (strong[ch[i].ver[j]] != ch[i].ver[j + 1])
ch[i].weak.insert(j);
}
}
cin >> q;
for (int i = 0; i < n; i ++)
ans = (ans + dp[i][0] + dp[i][1]) % mod;
cout << ans << endl;
for (int i = 0; i < q; i ++)
{
///if (i % 10000 == 0)
// cout << "YEP" << endl;
int v;
ll d;
cin >> v >> d;
///update(v, d);
update_edge(v, d);
cout << ans << endl;
}
}
int main()
{
///freopen("input.txt", "r", stdin);
speed();
solve();
return 0;
}
Compilation message
arboras.cpp: In member function 'void chain::build_chain()':
arboras.cpp:87:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
87 | for (int i = 0; i < ver.size(); i ++)
| ~~^~~~~~~~~~~~
arboras.cpp: In function 'void solve()':
arboras.cpp:469:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<chain>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
469 | for (int i = 0; i < ch.size(); i ++)
| ~~^~~~~~~~~~~
arboras.cpp:472:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<chain>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
472 | for (int i = 0; i < ch.size(); i ++)
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3028 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2900 KB |
Output is correct |
| 3 |
Correct |
2 ms |
3028 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
118 ms |
31316 KB |
Output is correct |
| 2 |
Correct |
73 ms |
32096 KB |
Output is correct |
| 3 |
Correct |
87 ms |
32780 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3127 ms |
30980 KB |
Output is correct |
| 2 |
Correct |
96 ms |
29936 KB |
Output is correct |
| 3 |
Correct |
98 ms |
32472 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
3028 KB |
Output is correct |
| 2 |
Correct |
2 ms |
2900 KB |
Output is correct |
| 3 |
Correct |
2 ms |
3028 KB |
Output is correct |
| 4 |
Correct |
118 ms |
31316 KB |
Output is correct |
| 5 |
Correct |
73 ms |
32096 KB |
Output is correct |
| 6 |
Correct |
87 ms |
32780 KB |
Output is correct |
| 7 |
Correct |
3127 ms |
30980 KB |
Output is correct |
| 8 |
Correct |
96 ms |
29936 KB |
Output is correct |
| 9 |
Correct |
98 ms |
32472 KB |
Output is correct |
| 10 |
Correct |
4454 ms |
30992 KB |
Output is correct |
| 11 |
Correct |
93 ms |
29836 KB |
Output is correct |
| 12 |
Correct |
113 ms |
32540 KB |
Output is correct |
| 13 |
Correct |
78 ms |
22352 KB |
Output is correct |
| 14 |
Correct |
80 ms |
22360 KB |
Output is correct |
