#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template<typename T> using ordered_set = tree< T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") //#pragma GCC target("avx,avx2,fma") #define ld long double #define F first #define S second #define all(v) v.begin(),v.end() #define pb push_back #define eb emplace_back #define endl '\n' #define pqueue priority_queue typedef pair<int,int> ii; typedef tuple<int,int,int> iii; typedef tuple<int,int,int,int> iiii; const int INF = 1e12; const int MOD = 998244353; const int maxN = 1100; using i64 = long long; template<typename T> using vec = vector<T>; int n,q,ans; vec<int> p; vec<i64> d, depth; vec<set<ii>> adj; vec<ii> top; vec<multiset<i64,greater<i64>>> sets; void dfs(int node,int p){ for (auto tp : adj[node]){ int to,w; tie(to,w) = tp; if (to == p) continue; dfs(to,node); int sm = w + depth[node]; sets[node].insert(sm); } d[node] = *sets[node].begin() + *next(sets[node].begin()); depth[node] = *sets[node].begin(); } int32_t main(){ ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr); cin >> n; p.assign(n,0); d.assign(n,0); depth.assign(n,0); adj.assign(n,set<ii>()); top.assign(n,{}); sets.assign(n,multiset<i64,greater<i64>>()); p[0] = -1; for (int i = 1; i < n; i++) cin >> p[i]; for (int i = 1; i < n; i++){ int w; cin >> w; top[i] = {p[i],w}; adj[p[i]].insert({i,w}); } for (int i = 0; i < n; i++){ for (int j = 0; j < 3; j++) sets[i].insert(0); } dfs(0,-1); cout << ans << endl; cin >> q; while (q--){ int v,add; cin >> v >> add; int tmpv = v; i64 tmp = depth[v] + add; bool changed = false; int old = depth[v]; while (p[v] != -1 && !changed){ int par = p[v]; auto &st = sets[par]; tmp += top[v].S; old += top[v].S; if (*st.begin() >= tmp){ changed = true; } st.erase(st.find(old)); st.insert(tmp); ans -= d[par]; d[par] = *st.begin() + *next(st.begin()); ans += d[par]; v = p[v]; depth[v] = *st.begin(); } top[tmpv].S += add; cout << ans << endl; } return 0; }

arboras.cpp:33:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+12' to '2147483647' [-Woverflow]
   33 | const int INF = 1e12;
      |                 ^~~~