问题
给定两个长度为 $n$ 的序列 $w_i,a_i$，需要求一个满足给定一系列偏序集关系的序列 $b_i$，使得 $\sum w_i|a_i-b_i|^k$ 最小。
$k=1$
对于 $k=1$ 的情况问题等价于求 $\sum w_i|a_i-b_i|$ 最小。对于偏序集是一条链的情况可以简单的使用 slope trick 解决，这里不再赘述。考虑更一般的情况。
我们定义问题 $S[l,r]$ 表示要求所有的 $l\leq b_i\leq r$ 情况时的子问题。可以发现，对于最终的最优解 $b_i\notin [l,r]$ 的情况，如果 $b_i<l$，那么对于 $S[l,r]$ 的问题，有$b_i=l$；$b_i>r$ 的情况类似。感性理解正确。
发现这个形式类似于整体二分。所以可以对 $b_i$ 进行整体二分，每次处理 $S[mid,mid+1]$，由于 $k=1$，$b_i$ 一定是整数，所以一定是一部分 $b_i=mid$，另一部分 $b_i=mid+1$。对于 $b_i=mid$ 的部分，真实的 $b_i$ 满足 $b_i\leq mid$，另一侧同理。所以可以递归到两个子问题解决，考虑子问题时由于内部和外部之间的偏序关系已经被保证了，所以不需要考虑这一部分内容，只需要考虑内部的偏序关系。也就是说，每次处理的内部是一个相对独立于外部的问题。
下面考虑怎么处理一个权值只有两种选择的问题。这是一个经典的最大权闭合子图问题，可以建图网络流解决。然后大概能跑 $n,m$ 几千级别的数据。
$k\geq 2$
对于 $k\geq 2$ 的问题，与上面最大的区别在于 $b_i$ 不一定是整数。如果我们要求 $b_i$ 是整数，那么一样做。否则可以实数二分，但是由于实数二分精度太差，还有另一种做法。考虑当前处理的是 $S[mid,mid+eps]$，那么 $eps$ 足够小，就可以认为这一段是一次函数，所以可以看做代价函数在 $mid$ 处的导数乘上 $eps$，加上 $mid$ 出的代价，同时减去在 $mid$ 出的函数值显然没有问题。所以可以再将代价除以 $eps$，所以就是 $0$ 和 $mid$ 处的导数值，这样就能提升精度了。
特殊情况
如果图是树，可以树形 dp 来代替网络流做到 $O(n\log n)$。如果是基环树，可以钦定环上一个点的值然后变成树。