P10573 [JRKSJ R8] C0mp0nents
题目背景
题目描述
小 I 有一张 $n$ 个点、$m$ 条边的无向图，保证图无重边、无自环。初始时第 $i$ 个点的点权 $a_i = i$。小 I 有一个额外的常量 $k$。
小 R 可以进行很多很多次操作。每次操作，她选择图上两个相邻的节点 $x, y$ 满足 $\lvert a_x - a_y \rvert = k$，随后小 I 会将 $a_x$ 设为 $a_y$。
对每个 $1 \leq s \leq n$，**如果在过程中不修改 $\bm{a_x = s}$ 的节点 $\bm x$ 的权值**，小 I 想知道：若干次操作后，图上最多有多少个点满足 $a_i = s$。
输入格式
无
输出格式
无
说明/提示
### 数据规模与约定
**本题采用捆绑测试。**
- Subtask 0（0 pts）：样例；
- Subtask 1（5 pts）：$n \leq 200$，$m \leq 400$；
- Subtask 2（20 pts）：$n \leq 5000$，$m \leq 10^4$；
- Subtask 3（25 pts）：$n \leq 10^5$，$m \leq 3\times 10^5$；
- Subtask 4（50 pts）：无特殊限制。
对于所有数据，满足 $1 \leq k \leq n \leq 4\times 10^5$，$1 \leq u, v \leq n$，$0 \leq m \leq 10^6$，保证图无重边、无自环。