#P10573. [JRKSJ R8] C0mp0nents
[JRKSJ R8] C0mp0nents
题目背景
题目描述
小 I 有一张 个点、 条边的无向图,保证图无重边、无自环。初始时第 个点的点权 。小 I 有一个额外的常量 。
小 R 可以进行很多很多次操作。每次操作,她选择图上两个相邻的节点 满足 ,随后小 I 会将 设为 。
对每个 ,如果在过程中不修改 的节点 的权值,小 I 想知道:若干次操作后,图上最多有多少个点满足 。
输入格式
第一行三个整数 。
接下来 行,每行两个整数 ,依次表示一条连接 的边。
输出格式
一行 个整数,第 个整数表示 时的答案。
提示
数据规模与约定
本题采用捆绑测试。
- Subtask 0(0 pts):样例;
- Subtask 1(5 pts):,;
- Subtask 2(20 pts):,;
- Subtask 3(25 pts):,;
- Subtask 4(50 pts):无特殊限制。
对于所有数据,满足 ,,,保证图无重边、无自环。