#include <bits/stdc++.h> #include "tree.h" using namespace std; using ll = long long; using pii = pair<int, int>; int n; std::vector<int> p, w; struct SegTree { vector<int> tree; void init() { tree.assign(4*n, 0); } void query(int p, int l, int r, int i, int x) { if (l>i || r<i) return; if (l==r) { tree[p] = x; return; } int m = (l+r)/2; query(2*p, l, m, i, x); query(2*p+1, m+1, r, i, x); int i1 = tree[2*p]; int i2 = tree[2*p+1]; if (i1==-1) { tree[p] = i2; return; } if (i2==-1) { tree[p] = i1; return; } if (w[i1] < w[i2]) tree[p] = i1; else tree[p] = i2; } int rmq(int p, int l, int r, int i, int j) { if (l > j || r < i) return -1; if (i <= l && r <= j) { return tree[p]; } int m = (l+r)/2; int i1 = rmq(2*p, l, m, i, j); int i2 = rmq(2*p+1, m+1, r, i, j); if (i1==-1) return i2; if (i2==-1) return i1; if (w[i1] < w[i2]) return i1; else return i2; } }; SegTree st; vector<vector<int>> adj; vector<int> leaf; vector<int> in, out; vector<bool> isleaf; int t; void dfs(int u, int p=-1) { bool can = true; in[u] = t++; for (auto x : adj[u]) { if (x==p) continue; dfs(x, u); can = false; } out[u] = t; if (can) { leaf.push_back(u); isleaf[u] = true; } } void init(std::vector<int> P, std::vector<int> W) { p = P; w = W; n = (int)p.size(); adj.assign(n, {}); in.assign(n, 0); out.assign(n, 0); isleaf.assign(n, false); t=0; for (int i=1; i<n; i++) { int a = i; int b = p[i]; adj[a].push_back(b); adj[b].push_back(a); } t=0; dfs(0); } long long query(int L, int R) { vector<ll> c(n, 0); vector<ll> S(n, 0); st.init(); for (int i=0; i<n; i++) { if (!isleaf[i]) st.query(1, 0, n-1, in[i], i); else st.query(1, 0, n-1, in[i], -1); } for (int i=n-1; i>=0; i--) { if (isleaf[i]) { c[i] = L; S[i] = L; } else { while (S[i] > R) { int idx = st.rmq(1, 0, n-1, in[i], out[i]-1); S[idx]--; S[i]--; c[idx]--; if (S[idx] == L) st.query(1, 0, n-1, in[idx], -1); } if (S[i] == L) st.query(1, 0, n-1, in[i], -1); } if (i==0) continue; S[p[i]] += S[i]; } ll ans=0; for (int i=0; i<n; i++) { ans += abs(c[i])*w[i]; } return ans; }