[ICPC 2022 Nanjing R] 工厂重现 - 洛谷P14160
这个题应该是这个题的加强版，其实差不多。
标签
Minkowski, 平衡树把一条路径拆到每条边的贡献，若 \(u\) 的子树内有 \(c\) 个黑点，\((u, fa_u)\) 的贡献是 \(c(k - c)\)
令 \(f_u(i)\) 表示 \(u\) 的子树内选取 \(i\) 个黑点的答案。
合并子树时，\(f_u(i) = \min \{ f_v(j) + wj(k - j) + f_u(i - j) \}(w 为 (u, fa_u) 边权)\)。
令 \(g_v(j) = f_v(j) + wj(k - j)\)，很显然是一个闵可夫斯基和的形式。
考虑 \(f, g\) 的差分数组，\(\Delta g_v(j) = \Delta f_v(j) - 2wj + (k + 1)w\)。这玩意怎么搞？
为了保证维护差分数组的从小到大排序的顺序（归并），同时加的东西与 \(j\) 相关，只能使用平衡树了，打个懒标记即可。
因为两棵树没有什么性质，还是要启发式合并，把 \(sz\) 小的那棵上的节点一个一个丢大 \(sz\) 大的。所以时间复杂度：\(O(n \log^2 n)\)
因为蒟蒻只会 FHQ，所以说说写 FHQ 的坑点（可能不太清楚，可以忽略）：
split, Merge时都需要下传懒标记，否则少了/多了一个儿子以后下传有 \(bug\)。- 不妨设一次项、常数项的 \(tag\) 分别为
tagk, tagb。为了保证下传时的 \(j\) 还是原来的 \(j\)（因为经过split, Merge后的 \(sz\) 不太可靠），可以update时直接把tagk * c直接加入到tagb，而不是每次开一个 \(sum\) 记录当前节点前面还有几个节点。
void update(int c, int x, int k, ll s) {if (!x) return;s += 1ll * c * k, tr[x].val += s + 1ll * rnk(x) * k;tr[x].tagk += k, tr[x].tagb += s;
}