信友队 CSP-S2023 D

\(h\) 的存在暗示我们从后到前增量来做。

考虑建出失配树，则对于树上两点 \(x,y\)，设 \(a_x\) 表示 \(x\) 到根的长度之和，则两者的绝对代价即为 \(\max(a_x,a_y)-a_{lca}\)。显然可以把两部分拆开来做。

每次插入节点，一定会把它作为原树的一个新叶子。对于 \(\max(a_x,a_y)\)，其实就要求我们在插入当前 \(x\) 时，对于原本树上的节点 \(y\)，若 \(a_y\le a_x\)，计贡献 \(a_x\)，否则计贡献 \(y\)。于是数据结构维护下前缀大小 \(a\) 的个数和后缀大小 \(a\) 的权值和即可。

对于 \(a_{lca}\)，考虑插入叶子 \(x\) 时，计 \(x\) 的 \(p\) 级祖先为 \(x_p\)，则贡献为 \(\sum_{i=1}^k(siz_{x_i}-siz_{x_{i-1}})\times a_{x}\)。把 \(a_x\) 作差分即可将贡献变为 \(\sum_{i=1}^k siz_{x_i}\times a_{x}'\)。对于这个式子，数据结构动态维护下链 \(siz\) 和/修改即可。

时间复杂度 \(O(m\log n^2)\)。

拆贡献，差分。