洛谷上的几篇题解都有些不知所云，所以自己写一篇，顺便加深一下对这个很久以前就见过但是现在才理解的套路。
下文中 $(u,v,w,c)$ 表示一条 $u\rightarrow v$ 流量为 $w$ 代价为 $c$ 的边。
首先移动点权需要代价这个东西可以套路地用费用流刻画，建图 $(S,u,a_u,0)(u,v,\infty,w)(u,T,b_u,0)$，其中满足 $(u,v,w)\in E$。跑最小费用最大流即可，复杂度不知道，反正过不去这道题。
考虑简化一些费用流模型，把边权的费用考虑放在 $u,v,lca(u,v)$ 三个点上面，那么把一个点从 $u$ 挪到 $v$ 的代价就是 $dep_u+dep_v-2dep_{lca(u,v)}$。这样做的好处是把边权变成了点权，所以建图也需要拆点。具体的，建图 $(S,u_1,a_u,dep_u)(u_1,fa_{u_1},\infty,0)(u_1,u_2,\infty,-2dep_u)(fa_{u_2},u_2,\infty,0)(u_2,T,b_u,dep_u)$，跑最小费用最大流。
发现这个模型仍然不好模拟费用流，主要原因在于最大流这个条件限制了流量比较烦人，考虑去掉这个条件。考虑对于每一组匹配 $(u,v)$，把它的权值减去 $\infty$，最后加回去即可，这样的话，最小费用最大流就可以转化为求最小费用循环流，也可以说是消去图中所有负圈。
这样建边之后，就可以用两个小根堆来维护，一个堆维护当前节点 $u$ 的后代指向它的所有边，另一个维护它指向它的所有后代的所有边（均包括自己）。每次只需要从两个堆顶拿出来一个元素看一下这组匹配的大小是否 $<0$ 即可。如果是就加进答案并把反悔边加入堆中。由于需要合并儿子节点，用左偏树维护。时间复杂度 $O(\sum y\log \sum y)$。
标签：费用,infty,dep,P6943,最小,建图,lca From： https://www.cnblogs.com/Harry27182/p/17971168