比赛：CF2131 Div.3

chenwenmo · 2025-08-12 20:15:38 · 题解

CF2131 Div.3

缩成直径最小的时候就是菊花图。

考虑固定菊花图的中心，把该中心设为树根，那么每次操作 (s,t) 时，s 一定为根，t 一定为叶子，答案就是以该点为根时，与根距离 >1 的叶子数量。考虑证明：

假定这个不是答案，只是我们给树定义了一个权值。
菊花图的权值为 0，不是菊花图的树权值一定 >0。
假设操作了一次 (s,t)，
- 若 s 不为根，那么树权值一定不减。
- 若 s 为根，但 t 不为叶子，那么树的权值不变。
- 否则 s 为根，且 t 为叶子，树的权值刚好减一。
综上所述，树的最小操作次数就是该树的权值。

然后用简单换根 DP 即可 O(n) 解决。

Code

每个 i 只能操作一次，也就是每个 i 必须一步到位，那么只需考虑 i 能从 i+1 处取什么来异或。发现要么不取，要么取 b_{i+1}，要么取 a_{i+1}，因此 O(n) check 即可。

Code

假设要走到 (x,y)，那么 a[1,x] 和 b[1,y] 必须都变成同一个数。

因此记一下 a0(i),a1(i),b0(i),b1(i) 表示前缀 0,1 个数，答案就是 \min(a0(x)+b0(y),a1(x)+b1(y))。

枚举 x，考虑如何计算贡献。推一下式子：

\begin{aligned} a0(x)+b0(y)&<a1(x)+b1(y) \\ a0(x)-a1(x)&<b1(y)-b0(x) \end{aligned}

于是拿桶预处理一下即可。

Code

设 f(i) 表示完全删掉 i 需要多少步，f(1)=1，f(i)=1+\sum\limits_{j=1}^{i-1} f(j)，发现可以把值域缩小到 O(\log k) 级别。

因此直接暴力模拟即可。复杂度大概是 O(n\log n + \log^2 k)。

Code