CF1943C 题解

EuphoricStar · 2024-03-20 08:58:52 · 题解

发现对于一条链，一次操作最多能染黑这条链上的 2 个点。

所以我们把直径拎出来，设直径长度为 d。

考虑一条长度为 d 的链至少要多少次能全染黑。

• 若 d 为奇数，显然从直径中点 u 开始做 (u, 0), (u, 1), \ldots, (u, \frac{d - 1}{2}) 即可。这样操作次数已经顶到下界了，而且发现由直径的性质，这样能把整棵树都全部染黑。
• 若 d 为偶数，发现 d = 2 和 d = 4 时都需要 2 次。考虑若 d \bmod 4 = 0，可以找到直径的中心边 (x, y)，依次做 (x, 1), (y, 1), (x, 3), (y, 3), \ldots, (x, \frac{d}{2} - 1), (y, \frac{d}{2} - 1) 即可，只需 \frac{d}{2} 次操作。若 d \bmod 4 = 2，只能做 (x, 0), (x, 1), \ldots, (x, \frac{d}{2})，需要 \frac{d}{2} + 1 次操作。

找直径即可。时间复杂度 O(n)，开 2 \times 10^3 是因为 checker 要 O(n^2)。

code