CF1467E Distinctive Roots in a Tree

突然发现深究一些树上问题还是挺有意思的哈。

显然对于同一种权值的任意两个结点，其两端的部分都是不合法的。

维护两个标记表示子树内均不合法与子树外均不合法即可。但相同权值的点对数量是 \(O(n^2)\) 的，我们要优化这个过程。

发现很多点对都是无用的。DFS 下去，遇到一个 \(x\) 权值的结点 \(u\)，其实只需要与上一个遇到的 \(x\) 权值的结点 \(v\) 做一下就好了，原因如下：

• \(v\) 是 \(u\) 的祖先。\(u\) 与 \(v\) 子树外的结点做没有影响。
• \(v\) 不是 \(u\) 的祖先。不经过 \(x\) 权值的结点直接走到 \(u\) 的除 \(v\) 外的结点一定已经做过了且它们与 \(u\) 做没有影响。
  

红色结点表示 \(x\) 权值的结点，蓝色结点就是 \(u\)。

画图就会发现这个结论太容易得出啦。

最后再来一次 DFS 处理所有标记。记一下是否存在子树外均不合法标记和当前暂时合法的子树内合法结点数。当一个结点的两个儿子中都出现子树外均不合法标记时答案一定为 \(0\)。细节仔细思考一下。

时间复杂度 \(O(n\log n)\)，瓶颈在于离散化。

多说一句，其实只要那些红色的点都做过就行了，具体谁与谁做无所谓。所以写成都与最上面那个祖先做会方便一点。