题解：CF2042E Vertex Pairs

钦定根妙完了。

因为原题给出了一个无根树，如果我们在此基础上考虑不选择一个点，则需要对其的所有子树进行递归，这个做起来是十分复杂的。所以我们考虑钦定一个点为根，表示根这个点一定在我所选的集合内。因为同一种颜色的两个点至少选择一个，所以将两个点分别钦定为根跑一遍即可。

因为删除第 $i$ 个点的代价为 $2^i$，所以我们考虑贪心，按照编号从大往小进行考虑，贪心的可以不选当前第 $i$ 个点就不选，显然这一定是最优的。

那么对于一个节点，如果删除了它相当于删除了它的所有子树，那么我们考虑如何判断那些点不能被删除。

第一种情况可以提前找到所有同色点 $\text{lca}$ 预处理，第二种情况可以直接打标记暴力删除。

因为每个点只会被删除一次，所以复杂度是正确的。

复杂度 $O(n \log n)$。