题解：CF2042E Vertex Pairs

· · 题解

钦定根妙完了。

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

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

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

  1. 任意一对同色点的 \text{lca} 到根路径上的所有点是不能被删除的。

  2. 当一个点被删除，则另一个同色点到根路径上的所有点是不能被删除的。

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

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

复杂度 O(n \log n)。