题意
给你一棵树，树根为 \(1\)。点 \(u\) 有点权 \(c_u\)，可以花费 \(k\) 的代价使得 \(c_u\) 加上或减去 \(k\)，求使得整棵树满足父亲的点权严格大于儿子的点权时，需要花费的最小代价。
题解
我们先给每个点的点权 \(c_u\) 加上 \(u\) 的深度之后在操作，这样就可以将题意中的严格大于变为不小于，且答案不变。下文所述的 \(c_u\) 均为这样操作后的点权。
算法一
我们记 \(f_{u,i}\) 代表考虑完 \(u\) 的子树，方案合法时，\(u\) 的点权为 \(i\) 的最小代价。记 \(g_{u,i}\) 代表考虑完 \(u\) 的子树，方案合法时，\(u\) 的点权小于等于 \(i\) 的最小代价。显然有：
\[
g_{u,i}=\min_{j\le i}f_{u,j}
\]
对于节点 \(u\)，先计算它儿子的答案，然后我们令 \(f_{u,i}=|i-c
_u|\)，再从它的儿子处合并，枚举 \(u\) 的儿子 \(v\)，则：
\[
f_{u,i}\leftarrow f_{u,i}+g_{v,i}
\]
最后的答案就是 \(\displaystyle \min
g_{1,i}\)。这样我们就有了一个 \(O(nV)\) 的做法，其中 \(V\) 是点权范围，可以通过子任务一。
算法二
我们将上述的 \(f_{u,i},g_{u,i}\) 看作一个关于 \(i\) 的函数，考虑它们的函数图像长什么样子。由于给所有的 \(c_u\) 同时加上一个数不影响答案，我们可以先将所有的 \(c_u\) 调整为正，则此时函数 \(i<0\) 的部分没有意义（设最终答案中有若干个 \(c_u\) 取了负数，显然将它们变为 \(0\) 会更优），于是我们可以只考虑 \(i\ge 0\) 的部分。
考虑一个叶子节点 \(u\) 的 \(f_u,g_u\)。 \(f_u\) 的函数图像与纵轴的交点函数值为 \(c_u\)，在 \([0,c_u]\) 的斜率为 \(-1\)，在 \([c_u,+\infty]\) 的斜率为 \(1\)。由 \(g_u\) 的定义可知，\(g_u\) 即为 \(f_u\) 将 \([c_u,+\infty]\) 的斜率调整为 \(0\) 的结果，即 \(g_{u,i}=f_{u,c_u}(i>c_u)\)。
则对于一个非叶子节点 \(u\)，记 \(f'_{u,i}=|i-c_u|\)，则
\[
f_{u}=f'_u+\sum_{v\in son(u)}g_{v}
\]
记 \(size_u\) 是 \(u\) 的子树大小，\(sum_u\) 为 \(u\)
的子树权值和，结合上文对于叶子节点的分析可以知道 \(f_{u}\) 与纵轴交点处的函数值为 \(sum_u\)，斜率为 \(-size_u\)，并且斜率一路递增至 \(1\)，这启示我们维护 \(f_u\)
的拐点。同叶子节点的分析，可以得到，对于任何节点 \(u\)，其 \(g_u\) 都是 \(f_u\) 删掉最后一个拐点得到的。
于是我们可以用可并堆维护 \(f_u\) 的拐点，初始时，应往堆中放入两个 \(c_u\)，代表当前函数斜率在 \(c_u\) 处增加了 \(2\)。在与儿子合并完后，为了向父亲贡献，我们需要将当前堆中的拐点转换为 \(g_u\) 的拐点，即弹出最大的元素。
时间复杂度 \(O(n\log n)\)，可以通过所有测试点。
代码如下（具体实现的时候，我将 \(c_u\) 都调整为了非负，这可能会导致产生 \(i=0\) 时的拐点，但不影响正确性。其余内容与上文一样）：
using ll = long long; const int N = 1e5+7;
int n , dep[N]; ll sum , mn , c[N];
__gnu_pbds::priority_queue<ll> q[N];
vector <int> g[N];
void dfs(int u)
{
q[u].push(c[u]); q[u].push(c[u]);
for (auto v : g[u]) {
dfs(v); q[u].join(q[v]);
} q[u].pop();
}
void main()
{
cin >> n >> c[1]; sum = c[1];
for (int i = 2 , p; i <= n; i++) {
cin >> p >> c[i]; dep[i] = dep[p] + 1;
c[i] += dep[i]; mn = min(mn , c[i]);
g[p].push_back(i); sum += c[i];
} dfs(1);
while(!q[1].empty()) {
sum -= q[1].top(); q[1].pop();
} cout << sum << '\n';
}