POD 题解

考虑每种颜色都只在一条链上出现这个限制。

考虑使用随机化 \(\text{hash}\)，我们对每个点随机一个权值，使得每种颜色所有点异或值为 \(0\)。

这样一种颜色如果只在一条链上，那对两条链 \(\text{hash}\) 异或值的贡献就是 \(0\)，否则就是两个随机值。

这样如果存在一个颜色存在于两条链上，那两条链的 \(\text{hash}\) 异或值就是两个随机值，否则就都是 \(0\)。

那么每种颜色都只在一条链上出现就等价于每条链异或值为 \(0\)。

然后的问题就是简单的了，考虑断还为链，问题变为取一个区间，异或和为 \(0\)，做个异或前缀和随便搞搞就行了。

精细实现可以容易做到时间复杂度 \(\Theta(n)\)。