B4588 [CSP-X 2026 河南] 颜色预测 / predict
题目描述
有 $n$ 个城市,每个城市都被染成黑色或白色。城市之间有 $m$ 条双向公路,任意两个城市之间都可以通过这些公路互相到达。两个城市之间的距离定义为从一个城市到另一个城市所需经过的最少公路数量。
对于一个奇数 $k$,每个城市的市长都会按如下方式预测自己城市的颜色:将除本城市以外的所有城市按“到本城市的距离”为第一关键字、“城市编号”为第二关键字从小到大排序,取排在最前面的 $k$ 个城市作为参考城市。由于 $k$ 是奇数,这 $k$ 个参考城市中黑色城市与白色城市的数量一定不相等:若黑色城市更多,则预测本城市为黑色;若白色城市更多,则预测本城市为白色。
对于每个奇数 $k$($1\le k\le n-1$),请你求出能正确预测自己城市颜色的城市数量。
输入格式
输入的第一行包含两个用单个空格隔开的整数 $n,m$,表示城市数量和公路数量。
输入的第二行包含 $n$ 个用单个空格隔开的整数 $c_1,c_2,\ldots,c_n$,其中 $c_i=1$ 表示城市 $i$ 是黑色,$c_i=0$ 表示城市 $i$ 是白色。
接下来 $m$ 行,每行包含两个用单个空格隔开的整数 $u,v$,表示城市 $u$ 与城市 $v$ 之间有一条公路。
输出格式
输出一行 $\left\lfloor\frac{n}{2}\right\rfloor$ 个用单个空格隔开的整数,其中第 $i$ 个整数表示 $k=2i-1$ 时能正确预测自己城市颜色的城市数量。
说明/提示
### 样例 1 解释
$k=1$ 时,$1$ 号城市参考 $2$ 号城市,$2$ 至 $5$ 号城市都参考 $1$ 号城市。$1$ 号、$2$ 号城市本身是白色,它们的参考城市也是白色,因此预测正确;$3$ 至 $5$ 号城市本身是黑色,它们的参考城市是白色,因此预测错误。共有 $2$ 个城市预测正确。
$k=3$ 时,$1$ 号城市参考 $2,3,4$ 号城市,$2$ 号城市参考 $1,3,4$ 号城市,$3$ 号城市参考 $1,2,4$ 号城市,$4$ 号城市参考 $1,2,3$ 号城市,$5$ 号城市参考 $1,2,3$ 号城市。其中 $1,2$ 号城市的参考城市中黑色城市更多,它们预测自己为黑色,而实际上它们是白色;$3,4,5$ 号城市的参考城市中白色城市更多,它们预测自己为白色,而实际上它们是黑色。因此没有城市预测正确,答案为 $0$。
### 样例 2 解释
$k=1$ 时,$4$ 号城市参考距离最近且编号最小的 $1$ 号城市(白色),与自身颜色相同,预测正确;其余三个城市参考到的城市颜色都与自己不同,预测错误,共有 $1$ 个城市预测正确。
$k=3$ 时,每个城市都要参考除自己以外的全部 $3$ 个城市,其中有 $2$ 个城市与自己的颜色不同,因此预测结果都与自身颜色相反,没有城市预测正确,答案为 $0$。
### 子任务
对于全部测试数据,$2\le n\le 1000$,$n-1\le m\le\min\left(\frac{n(n-1)}{2},10^6\right)$,$c_i\in\{0,1\}$。保证任意两个城市之间都可以通过这些公路互相到达,且没有重边和自环。
本题采用捆绑测试:一个子任务中的全部测试点全部通过,才能得到该子任务的分值。
- 子任务 1(10 分):所有城市的颜色都是 $0$。
- 子任务 2(19 分):$n\le 100$。
- 子任务 3(30 分):$n\le 500$,且所有的公路构成一条链。
- 子任务 4(41 分):无特殊限制。