没看懂题解导致虚空调试三小时
（假设你看过了官方题解）
大概总结一下这个算法背后的直觉。
一堆同色点会覆盖两两之间的简单路径，我们要覆盖整棵树。不妨任意钦定一根，注意到每个点能覆盖的东西都是它的一些祖先，直到与配对点的 LCA 为止。注意到叶子节点很关键，一方面因为叶子边被截断难以处理，另一方面叶子结点和叶子配对更优，同时内部节点配对应当尽可能转化为叶子的配对。
然后贪心直觉是让每个叶子覆盖的尽量高。最高的覆盖就是覆盖到根节点，注意到这在大多数时候都可行。但如果某个子树内的点多于总数一半，就会爆炸。所以选择叶子意义的重心作为根。这样我们猜想确实可以让每个叶子都覆盖到根，考虑给出一种构造。
对于不同的颜色，我们不妨从多到少考虑它们，当然乱序并不影响。我们显然不能把这种颜色全部染进一个子树里。假设我们用这种颜色染了一些叶子，那么剩余的叶子仍然需要满足上面的不存在一个子树叶子过多的限制。一个理解是，当前颜色染色完毕之后，被染色的叶子就消失了，因为它们无法和其他叶子继续配对。
那么首先我们应当考虑两个在不同子树中的叶子。注意到对任意时刻，取不在最大子树中的叶子都可能导致限制被破坏，于是我们始终应该取剩余叶子数最多的子树。这个过程可以始终持续而满足同样的没有叶子数过多子树的性质。
注意到我们一直假设的是存在两个在不同子树中的叶子，但可能只剩下一个。这时我们被迫放弃将它与其他叶子配对，但我们可以挑选一个合适的内部点，只要内部点与叶子的路径通过根即可。不妨取根节点，即叶子意义下重心 $x$。
注意到所有被染色的节点都满足有不在同一子树中的配对点。而所有叶子都被染色，从而所有叶子到根的路径都被覆盖。对任意边，它必定位于某个叶子到根的路径上。于是每条边必然被覆盖，得到了合法的构造。