听说能 $4n-\Omega(\log_2 n)$，但是我不会。

首先先会一下 $5n+\Theta(1)$：每次选择两个目前度数都不超过 $1$ 的两个点求一下之间的方向，直到无法操作，摊一下每个点最多带来两次，所以这部分是 $2n$，然后剩下至多三个点，暴力检查一下是至多 $5n+\mathcal{Theta}(1)$ 次。

再会一下 $5n-\log_2 n+\Theta(1)$：你可以用完全二叉树结构打擂台给 $n-1$ 个点找到一个出度，然后剩下一个点被检查了 $\log_2(n)+\Theta(1)$ 次，你最终如果剩下三个点必然包含它，于是提前做的这部分代价可以省去。

再会一下 $5n-3\log_2 n+\Theta(1)$：找到一个点后还能继续打擂台，把 $n-1$ 个点找到的出点设为父亲，做黑白染色，对黑点和白点（不算根）分别跑完全二叉树打擂台，然后打擂台出来的两个点和根是可用的候选点，都至少检查了 $\log_2 n+\Theta(1)$ 次了，可以省去这么多。

然后你发现这三个点真正全需要检查的情况是它们在原本的树上是从上往下的一条长为三的链，看起来就十分有用。

先得到一个 $4.5n+\mathcal{o}(n)$ 的算法：先打出和根同色的那个擂台，糟糕的情况只发生在赢的人深度为 $2$，然后还需要它的父亲是另一种颜色的胜者，于是你就对另一种颜色做一个从它的父亲开始一个接一个的比，这样如果是糟糕情况这个父亲肯定打完了这一侧的点，然后（看起来）黑白是均匀的（至少当 $n=2^k$ 时是一定均匀的），所以省去了一半。

然后再看看能不能再省省先进行的那一侧。

得到一个 $4n+\Theta(\log^2 n)$ 的做法：糟糕的情况只在深度为 $2$ 的点中发生，这只有 $\Theta(log^2n)$ 个，你先做它们，发生最坏情况也只需要补上这部分，然后你除此之外省去了黑白两种颜色的点，这样 $n$ 上系数就是 $4$ 了。

进一步 $4n+\log_2 n+\Theta(1)$ 的做法：那你先做深度为 $1$ 的点，这里只会多 $\log_2 n$ 个，然后糟糕的情况必须发生在它的儿子里，也只有 $\log_2 n$ 个，再联系上你最开始减掉的 $\log_2 n$ 就是这样。

最后就是 $4n+\Theta(1)$ 的做法：你发现深度为 $1$ 的点中每个点的儿子数近乎是 $0\sim \log_2 n-1$ 的等差数列，先做儿子多的再做儿子少的就能使得需要补的前面检查次数和后面的儿子数加起来是 $\log_2 n+\Theta(1)$ 的，于是就被最开始省去的 $\log_2 n+\Theta(1)$ 次平掉了。