给定 \(n\) 个点的树，每次操作为选取 \(a,b,c\) 三个点，满足 \(a\) 和 \(b\) 有边，\(b\) 和 \(c\) 有边，然后执行如下：
求最小的操作次数使得原树存在度为 \(n-1\) 的点。
改成一次操作的定义为：
选择一个 \(a,b,c\)，然后将 \(a\) 和 \(c\) 合并成一个点 \(x\)，并给 \(x\) 增加一个儿子。
假定 \(b\) 为 \(a,c\) 祖先，不难发现所有点的深度都不会变。
如果 \(b\) 不为 \(a,c\) 祖先，可以发现所有点的深度 \(\mod 2\) 的值不会变！
对这张图进行二分图染色，发现每次操作实质为选定一个黑-白-黑/白-黑-白三元组，然后变成 白-黑-白/黑-白-黑 的形式。
所以操作次数的下界是 \(\min(A,B)-1\)，其中 \(A\) 为黑点数，\(B\) 为白点数。
原文：https://www.cnblogs.com/Soulist/p/13662175.html