CSP-S2022模拟赛1 10.04

yzxoi

2022-10-04 (Updated: 2022-10-04)

A

相当于每次可以将一个数加上 $[C,D]$，或者减去 $[C,D]$。

枚举加上 $i$ 次，减去 $n-i-1$ 次，因此最后的值域区间为：
$$
[C\times i - (n-i-1)\times D, D\times i - (n-i-1) \times C]
$$
62428

注意到答案一定很小，设 $f_{i,j}$ 表示左端点为 $j$，能合并出数字 $i$ 的右端点。
$$
f_{i,j}=f_{i-1,f_{i-1,j}}
$$
88502520

需要遍历的点一定是在最小的包含白点的连通块内。

剩余的树上每个点都必须经过。因此除了起点与终点之间路径上的边会被经过恰好一次以外，其余所有边都会被经过恰好两次。

不妨先设所有边都经过了两次，若无修改每个点颜色即为初始颜色异或度数奇偶性，只需在其为白时进行一次修改操作。

然后考虑起点与终点之间的路径，它的影响是让路径上的点（包含起点但不包含终点）都被少经过一次。

容易发现，原本为白操作次数减 $2$，原本为黑色操作次数不变。

于是类似找树的直径即可。

设 $g_i$ 为 $i$ 到最近叶子的距离。

如果 $u$ 为根，$d_i\ge g_i$ 则 $i$ 子树内仅需贡献 $1$ 即可拦截 $u$，注意到如果 $i$ 的父节点 $f_i$ 能拦截 $u$ 则没必要动用 $i$，所以我们令 $d_i\ge g_i \land d_{f_i}< g_{f_i}$。

考虑点分治，根据分治重心我们可以划分成一个点及若干子树。

考虑每个子树对子树外的贡献，以及分治重心对所有子树的贡献。

注意一下一开始钦定的限制条件，不然可能重复计算。