/**
____ ____ ____ ____ ____ ____
||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;
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][1];
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;
}
}
}
ll ans = 0;
struct chain
{
vector < int > ver;
vector < pair < ll, ll > > st;
set < int > weak;
vector < pair < ll, ll > > tree, lazy;
pair < ll, ll > merge_node(pair < ll, ll > nd1, pair < ll, ll > nd2)
{
pair < ll, ll > nd;
nd.first = nd1.first + nd2.first;
nd.second = nd1.second + nd2.second;
return nd;
}
void build_tree(int root, int left, int right)
{
if (left == right)
{
tree[root] = st[left];
return;
}
int mid = (left + right) / 2;
build_tree(root * 2, left, mid);
build_tree(root * 2 + 1, mid + 1, right);
tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
}
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);
}
}
tree.resize(ver.size() * 4);
lazy.resize(ver.size() * 4);
build_tree(1, 0, (int)st.size() - 1);
}
};
vector < chain > ch;
void hld(int v)
{
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 base = dp[v][0], 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];
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];
dp[par[v]][1] = cur;
break;
}
ans = ans + cur - dp[par[v]][1];
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 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();
cin >> q;
for (int i = 0; i <= n; i ++)
ans += dp[i][0] + dp[i][1];
cout << ans << endl;
for (int i = 0; i < q; i ++)
{
int v;
ll d;
cin >> v >> d;
update(v, d);
cout << ans << endl;
}
}
int main()
{
solve();
return 0;
}
Compilation message
arboras.cpp: In member function 'void chain::build_chain()':
arboras.cpp:90:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for (int i = 0; i < ver.size(); i ++)
| ~~^~~~~~~~~~~~
arboras.cpp: In function 'void update(int, ll)':
arboras.cpp:138:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
138 | if (v == 0)
| ^~
arboras.cpp:140:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
140 | cur = cur + dis[v];
| ^~~
arboras.cpp:134:8: warning: unused variable 'base' [-Wunused-variable]
134 | ll base = dp[v][0], cur = dp[v][0];
| ^~~~
arboras.cpp: In function 'void solve()':
arboras.cpp:195:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<chain>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
195 | for (int i = 0; i < ch.size(); i ++)
| ~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
274 ms |
38824 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
704 ms |
38636 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
2928 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
