CF1394D Boboniu and Jianghu
一条边一划的话每个点会计算度数次，可以进行合并。树形 DP，记 $f_{i,0/1}$ 为考虑 $i$ 的子树，$i$ 向上引出单增/降的链的最小代价。
合并一次代价减 $a_u$，先儿子先都取最小，然后贪心选能变化且代价最小的。如果非根的话，那么向上引也会减一次。
哦，也可以看成给高度相同的链确定方向，这个理解好。可以儿子先全取 $0$。可以将第二维意义改为父亲的边指什么。
树形 DP 是这样的，分析性质就比较好做。
CF1179D Fedor Runs for President
选 $u,v$，增加的就是选两个点分别到 $u,v$ 使得路径的点无交。将 $u,v$ 路径上的边删掉，形成森林，记每棵树点数为 $a_i$，增加的是 $\frac{n^2 - \sum a_i^2}{2}$。需要最小化 $\sum a_i^2$。
树形 DP，$f_{i}$ 表示考虑 $i$ 的子树，$i$ 到父亲的边断掉的最小值，不断就是 $siz_u^2$。合并形如求 $\max(f_1 + f_2 + 2siz_1 \times siz_2)$ 需要斜率优化，单调栈维护下凸壳。桶排就 $O(n)$ 了吧。
不是这为啥黑啊？*2700。
CF1626E Black and White Tree
？？？显然不会来回走，然后就是一个类似最近点的东西，换根就做完了吧。呵呵，读错题了 😅。
注意到是不能与上一次选择的相同，记 $f_i$ 为 $i$ 能否到子树的黑点，满足以下三个条件之一即可
- $c_i=1$。
- $\exists son,c_{son}$。
- $\exists son, f_{son}=1,siz_{son} \ge 2$。
CF1016F Road Projects
类似第二道，把 $1 \to n$ 的链抽出来，然后就。哦，能在子树中连就在子树中连。
质量好低。