【题解】[UOJ-207] 共价大爷游长沙

[UOJ-207] 共价大爷游长沙

给定一棵 $n$ 个节点的树,和一个初始为空的点对的集合 $S$,有 $m$ 次操作,需要支持 $4$ 种操作:

  1. 断开一条边,再加入另一条边(保证仍然是树)。
  2. 在点对集合 $S$ 中加入点对 $(x,y)$。
  3. 在点对集合 $S$ 中删除第 $i$ 个加入的点对。
  4. 给定 $(x,y)$,询问若把集合中的点对看做树上路径,集合中所有路径是不是都经过边 $(x,y)$。

$1\le n\le 10^5,\ 1\le m\le 3\times 10^5$,任何时刻 $|S|\le 10$。

$\text{Solution:}$

考虑 $\text{LCT}$。

关键在于判断关键路径是否都经过边 $(x,y)$。观察发现,如果令 $x$ 是 $y$ 的父亲,那么若每条关键路径都恰好有一个端点在 $y$ 的子树中,就说明路径均会经过 $(x,y)$ 了。

考虑如何来计算一个子树内,每条关键路径的端点个数。容易发现这个判断类似异或,只有关键路径中恰好一个端点在子树内才合法,$2$ 个/$0$ 个都不合法。考虑随机化,给每条关键路径分配一个随机的值,具体来说,在关键路径的两个端点上,异或上这个随机值。由于 $|S|\le 10$,所以冲突概率是极小的了。

用 $\text{LCT}$ 维护子树内值的异或和,同时维护集合所有随机值的异或和,若两者相等,则说明子树内包括了所有路径的恰好一个端点。

至于 $\text{LCT}$ 维护子树信息,只需要加上维护虚子树的信息即可。只有在 $\text{access}$、$\text{link}$ 的时候,虚子树的信息才会改变,因此在这两个函数中各加一句维护虚子树信息即可。

时间复杂度 $\mathcal{O}(n\log n)$。


$\text{Summary:}$

毛爷爷nb!

本题的关键点在于使用异或来解决子树内关键路径端点个数的问题,使用随机的权值是十分巧妙的方式,因为这可以使得冲突几乎不会发生,这需要对 $|S|\le 10$ 的条件有足够的思考与认识。

因此,若出现需要快速判断集合是否相等,可以考虑随机分配权值之后维护异或和,但需要注意若集合中某元素出现个数为偶数,则方法失效(当然本题恰好运用了异或的这一性质,从而保证了子树内每条关键路径都只有一个端点)。

本题使用随机化,其方向在于降低冲突概率,思路值得借鉴。

添加新评论