记录一个人类智慧

· · 个人记录

要求比较两条树上路径的颜色数量大小（只需要求出谁大），满足其中一条的颜色数量是另一条的两倍及以上。支持修改单点颜色。

考虑在值域 $V$ 内均匀随机 $k$ 个值，最小值期望为 $\frac{V}{k+1}$。一条路径上有 $x$ 个颜色，最小值期望大小为 $\frac{V}{x+1}$。所以随机给每种颜色赋很多种权值，然后每次询问把两条路径上的每种赋权值得出的路径最小值求和。哪边和更小，即颜色数量更大。 具体做法树剖线段树求路径最小值。随机个 $50$ 次即可。时间复杂度 $O(50N+50Q\log^2N)$。