题解：P11634 [CTS2025] 仙人掌染色（暂无数据）

注意到对于同一个位置，交换相邻两项不会对总贡献产生任何影响，因此每个点的贡献只与相邻黑边个数有关，有 $n$ 条邻边其中 $k$ 条染黑时，产生 $g(n,k)=p\frac{nk(n-k)}{2}$ 的贡献。

考虑树的做法，直接在上面 dp：设 $f_{u,0/1}$ 表示 $u$ 子树中 $(u,fa_u)$ 是否染黑的最大收益。转移形如，选 $k$ 个取 $f_{v,1}$，剩下的取 $f_{v,0}$，最大化 $\sum f_{v,i}$。这是经典贪心，先取所有 $f_{v,0}$，然后选 $k$ 个 $f_{v,1}-f_{v,0}$ 最大的位置即可。进一步考虑边仙人掌的做法，首先建立圆方树，然后考虑环的问题怎么处理，注意到方点的儿子顺序对应的就是环的顺序，取出方点的父亲圆点 $u$ 以及在这个方点的邻边 $x,y$，发现只关心 $x,y$ 是否被选。再考虑下面的儿子，顺时针做一个 $2\times 2$ 的矩阵乘法状物：记录首条边，它上一条边是否被选的状态，然后讨论下一条边是否被选。因此转移的重点依然在圆点的统计，需要对于邻接圆点，方点决策，这是一个比树部分更复杂的贪心。

对于 $a_i<b_i-a_i$ 以及 $a_i\ge b_i-a_i$ 讨论。对于后者发现可以拆成两个重量为 $1$ 的独立物品。由于重量很小，经典结论是先考虑按照性价比贪心后，最终需要调整的部分很少。那么在此策略选 $a$ 后一定会立刻选 $b_i-a_i$，因此组合成 $\frac{b_i}{2}$ 性价比的物品。按照性价比排序后，考虑 $\ge k$ 的最小前缀和，如果是 $k$ 那么一定最优，否则是 $k+1$，只会删除已选重量为 $1$ 的 $\min(v_i)$ 或者删除重量为 $2$ 的 $\min b$，并加入未选取中重量为 $1$ 的最大收益的物品。这样容易对所有 $k$ 求出答案。这个子问题只需要排序，可以 $\mathcal O(m\log m)$。

视 $n,m$ 同阶，原问题容易做到时间复杂度 $\mathcal O(n\log n)$。