BZOJ5404 - party

和其他题解不太一样,这里没有用线段树……

首先肯定会在 LCA 处集合,通过树剖 + bitset 维护出可选的集合。然后利用 Hall 定理进行完美匹配统计答案。可以发现直接树剖 + 暴力跳是 $O(n ^ 2)$ 的,所以限制树链的长度至多为 $S$ ,则复杂度为:$O(n + qcS\times\frac{m}{32} + qc \times \frac{n}{S} + q \times 2^c \times \frac{m}{32})$ ,取 $S = \sqrt n$ 。

然后跑的飞快 233333.

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×