ARC107F Sum of Abs

先强制将所有点删去，然后考虑加点，将一个点拆成正点和负点，点权分别为 \(A_i+B_i\) 和 \(A_i-B_i\)，建图将问题转化为了求新建出图的最大全独立集。

这里因为点权可能是负的，对于负点权的点直接加进最小权点覆盖里就行了。

AGC029E Wandering TKHS

考虑哪些 \(v\) 对 \(u\) 产生贡献。设 \(w=lca(u, v)\)。

从 \(u\) 开始，必须要选到 \(w\) 才可能选 \(v\)。所以可以将问题转化到 \(w\) 上。

能选到 \(v\) 当且仅当 \(w\) 到 \(1\) 的路径（不含 \(w\)）上的最大值大于 \(v\) 到 \(w\) 路径（不含 \(w\)）上的最大值。

只需要遍历时记录当前到根的链的最大值及其位置 \(p\) 就可以了。特殊处理 \(p\) 位置能不能选，再记录一个次大值，次大值在 \(p\) 上面就可以选，否则不行。

一种码量非常小但是难以证明正确性的做法。建一个完全图，两点边权是他们需要满足性质的交集的大小。

跑一颗最大生成树后判断是否满足条件。正确性不明，但可以过。