P14135 【MX-X22-T6】「TPOI-4F」Miserable EXperience

把子树操作放到最后来做，且子树操作合法当且仅当 $\forall i,a_i \ge a_{fa_i}$。

先差分一下，令 $c_i = a_i - a_{fa_i}$，那么就是要让 $\forall i,c_i \ge 0$，答案就是 $\sum c_i$。一次行操作就是将第 $i$ 行的 $c$ 减 $1$，$i+1$ 行的 $c$ 加 $1$，代价变化 $cnt_{i+1} - cnt_{i} + 1$。所以每行只和点个数 $cnt_i$ 和 $c$ 的最小值 $p_i$ 有关。

先考虑 $p_i \ge 0$ 的情况，考虑把操作 $i,i+1,\ldots j$ 变为操作 $i,j$，代价为 $cnt_j - cnt_i + j - i$，设 $b_i = cnt_i + i$，即为 $b_j - b_i$。这样处理后就不存在形如 $(i,j),(j,k)$ 这样的重合操作了，所以每个点要么是只出，要么只进，对于只出的点，要求操作的次数 $\le p_i$（否则就小于 $0$ 了）。贪心地，把每个点按 $b_i$ 从小到大排序，每次取出最小的 $b_i$ 把前面没匹配的都和它匹配即可（也即每个点向其后缀最小值匹配）。

对于存在 $p_i < 0$ 的情况，可以先任意操作若干次将 $p_i$ 都变成非负数再继续调整，只要调整能最优，那么肯定可以到达最优答案。

考虑优化，由于只和后缀最小值之类的后缀信息相关，长链剖分后合并短链的时候大于短链长度的部分可以直接继承，前面直接暴力做就行。

实现方法可以用指针数组实现，方便很多。

复杂度 $\Theta(n)$。