【题解】[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$ 的条件有足够的思考与认识。

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

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