问题
有 \(n\) 个点，给出一张 DAG。
你需要给每个点设立权值 \(w_{1...n}\)，满足对于每条边 \((u,v)\) 都有 \(w_u\le w_v\)，求 \(\min\{\sum\limits_{i=1}^n b_i|w_i-a_i|^p\}\)，其中 \(a_i,b_i,p\) 是给出的。
整体二分
考虑二分 \(mid\)，把 DAG 划分为权值 \(\le mid\) 和 \(>mid\) 两部分，显然两个部分都是连通块。
这里有个结论：若每个权值只能取 \(mid\) 和 \(mid+1\)，那么得到的最优方案和最终答案中把 \(\le mid\) 的改为 \(mid\)，\(> mid\) 的改为 \(mid+1\) 后是一致的，具体证明详见 2018 年的高睿泉的集训队论文《浅谈保序回归问题》。
因此，我们只考虑每个点权值取 \(mid\) 还是 \(mid+1\)。我们钦定所有点都设为 \(mid\)，设 \(d_i=b_i|(mid+1)-a_i|^p-b_i|mid-a_i|^p\)，我们相当于在 DAG 中选取一个关于 \(d_i\) 的最小权闭合子图，然后把这些点设为 \(mid+1\)。
考虑最小割求解最小权闭合子图，然后求出两个点集 \(S,T\)，此时 \(S\) 中的点权值为 \(mid+1\)，\(T\) 中的为 \(mid\)，分治下去处理即可。