4.24 冲刺清北营 5
T1 吃粮
先考虑静态。
树上随机游走，写出转移方程：
这样只能 \(O(n^3)\) 高斯消元，注意到只有 \(f_{fa_{u}}\) 一个位置成环，套路性地考虑系数递推。
设 \(f_u=k_u\times f_{fa_u}+b_u\)，特别地，若 \(u\) 为叶子 \(k_u=0,b_u=a_u\)。
把式子改一下：
整理成：
于是有：
这样到 \(f_1\) 处时，因为此时没有 \(f_{fa_1}\) 项，所以 \(f_1=b_1\)。
这样复杂度降到 \(O(n)\)。
考虑如何带修，因为每次只求 \(b_1\)，所以只考虑对 \(b_1\) 的贡献，容易发现 \(k_u\) 与 \(a\) 无关，是常量。
对于修改一个非叶子节点 \(u\)，设修改变化量 \(\Delta a\)，对 \(b_u\) 的影响为 \(k_u\times deg_u\Delta a\)，再套到 \(b_{fa_u}\) 中，影响是 \(k_{fa_u}\times k_u\times deg_u\Delta a\)，因此对 \(b_1\) 的影响就是根链上所有 \(k\) 的累积乘 \(deg_u\Delta a\)。对于叶子节点，本身不再乘 \(k\) 即可。
T2 平衡
容易想到连边缩点。
之后是神秘做法。
一个点内的绝对值之和相当于是分段函数，构成了一个下凸包，很好维护。
易证明最终每个节点一定是出现过的 \(w\) 值，因此排序后分治，考虑满足 \(x\ge w_{mid}\) 的点集是什么。
接下来是更神秘结论：如果有 \(x_i\le x_j\) 的限制，则向 \(x_i\le x_j\) 连边，之后以 \(w_{mid}\) 在每个点对应取值的导数为点权，跑最小权闭合子图，则子图内的节点可以在最优条件下满足 \(x\ge w_{mid}\)，其余则不能。
证明：如果存在最小权闭合子图的一个子图满足其中节点 \(x_i<w_{mid}\)，而我们由小向大连边，因此不满足条件的节点也是类似拓扑的点集，因此除去这个子图剩下的部分仍然是闭合子图，而剩下的子图的点权和不小于原图，因此删去部分的点权和非正。
点权和的实际意义是斜率，而 \(x_i<w_{mid}\) 且下凸包斜率不降，所以对于每个节点，\(w_{mid}\) 处的斜率一定不小于 \(x_i\) 处斜率，而此时已知 \(w_{mid}\) 处斜率之和非正，因此 此时的结果一定不优于把 \(x_i\) 改为 \(w_{mid}\)。
网络流求最小权闭合子图即可。
另外斜率定义为 \(f(x)-f(x-1)\)，因此在不可导处的斜率取左极限。