1.偏序关系
设 $\preceq $ 是集合 \(S\) 上的一个二元关系，若 \(R\) 满足：
- 自反性：\(\forall x \in S\)，\(x \preceq x\) ；
- 反对称性：\(\forall x, y \in S\)， \(x \preceq y, y \preceq x \Rightarrow x = y\)；
- 传递性：\(\forall x, y, z \in S\)，\(x \preceq y, y \preceq z \Rightarrow x \preceq z\)。
2.问题描述
给定正整数 \(p\) 和一个偏序关系（DAG），每个点有权值 \((w_i, y_i)\)，你需要给每个点附上一个权值 \(f_i\)，使得 \(\forall x, y, s.t. x \preceq y\)，\(f_x \leq f_y\)，最小化回归代价：
\[\sum\limits_{i \in S}w_i|f_i - y_i|^p \]特别地，当 \(p \to \infty\) 时，回归代价为 \(\max_{i\in S}w_i|f_i - y_i|\)。
对于一个给定的 \(p\)，称上面的问题是 \(L_p\) 问题。
3.\(L_p\) 均值及其性质
定义 \(L_p\) 均值为使得 \(\sum_{i\in S}w_i|k - y_i|^p\) 最小的 \(k\)，即 \(f_i\) 均相同时的答案，可以对目标式求导，导数为 0 即是答案。
当 \(p = 1\) 时，\(L_1\) 均值是大家幼儿园都知道的带权中位数；当 \(p = 2\) 时，是带权平均数，即 \((\sum\limits_{i \in S}w_iy_i)/(\sum\limits_{i \in S}w_i)\) 。
当 \(p > 1\) 时，\(L_p\) 均值唯一。且对于任意一组 \(L_p\) 问题的最优解 \(\{f_i\}\)，存在 \(S\) 的一个子集 \(T\)，使得 \(T\) 的 \(L_p\) 均值为 \(f_i\)。
4.一般问题的算法
在 \(L_p\) 问题的基础上而外加入限制 \(S = \{a, b\}(a < b)\)，使得 \(\forall i, a \leq f_i \leq b\)。
\(p = 1\) 的情况
当 \(p = 1\) 时，一个点集 \(U\) 的 \(L_p\) 均值可能是一段区间，同时显然存在一个最优解使得 \(f_i \in \{y_i\}\) 中，移动 \(f_i\) 的改变量是一些一次函数。
引理 1 ：在 \(L_1\) 问题中，若存在区间 \((a, b)\) 使得所有 \(y_i\) 不在 \((a, b)\)，且存在一组最优解 \(z_i\) 使得 \(z_i\) 也不在 \((a, b)\)。定义一个集合对区间 \(S = (a,b)\) 取整为 \(z^S\)：若 \(z_i \leq a\)，\(z_i = a\)；若 \(z_i \geq b\)，\(z_i = b\)；否则不变。则 \(z^S\) 为 \(S\) 问题的一组最优解。
根据引理，可以进行整体二分。二分到 \([l, r]\) 时，计算 \(S = (y_{mid}, y_{mid+1})\) 的最优解，根据 \(z_i\) 的取值情况继续划分成 \([l, mid]\) 和 \([mid+1,r]\) 的两个子问题。
\(1 < p <\infty\) 的情况
当 \(1 <p < \infty\)，其 \(L_p\) 均值唯一，且代价函数在 \(< L_p\) 时递减，\(>L_p\) 时递增。
整体二分，找一个极小的 $\epsilon $ 使得任意 \(y_i, f_i\) 不在 \((mid, mid+\epsilon)\) 中，根据引理，每个 \(f_i\) 只能等于 \(mid\) 或 $mid+\epsilon $。 若 \(U\) 中任意一点选择了 $mid+\epsilon $，则所有满足 \(x \in U, i \preceq x\) 的点都只能选择 \(mid+\epsilon\)，等价于闭合子图模型。钦定所有点先选择 \(mid\)，若选择 $mid+\epsilon $ 的改变量为 \(w_i[(mid+\epsilon)^p - y_i]-w_i[mid^p - y_i]\) ，然后跑最小权闭合子图即可。
但可能精度误差较大。此时可以将 \(mid\) 看做变量 \(x\)，两边同时除以 \(\epsilon\)，变成 \(x\) 在 \(mid\) 时的导数，此时不会出现精度误差。
特殊情况的解法
对于树上的情况，可以 DP 维护分段函数，也可以直接整体二分后跑树形 DP。