并查集维护同色连通块

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")

#include <bits/stdc++.h>

题目内容

在一个社交网络中，有 $n$ 个用户，他们的好友关系构成一棵树。每个用户当前有两种状态之一：红色（用字符 R 表示）或白色（用字符 W 表示）。如果两个相邻的用户状态均为红色，则他们属于同一个红色连通块。请你找出所有红色连通块中，第 $k$ 大的连通块包含多少个用户。

数据范围：用户总数 $n$ 不超过 $10^5$，参数 $k$ 满足 $1 \le k \le n$。

输入描述

第一行包含两个正整数 $n$ 和 $k$。 第二行包含一个长度为 $n$ 的字符串，仅由字符 R 和 W 组成，其中第 $i$ 个字符表示第 $i$ 个用户的状态。 接下来的 $n-1$ 行，每行包含两个正整数 $u$ 和 $v$，表示用户 $u$ 和用户 $v$ 之间存在一条好友边。数据保证这些边组成一棵树，且 $1 \le u, v \le n$。

输出描述

输出一个整数。如果红色连通块的数量小于 $k$，输出 $-1$；否则输出第 $k$ 大的红色连通块包含的用户数量（大小相同的连通块各自独立计数）。

样例1

输入

5 2
RRFRF
1 2
2 3
3 4
4 5

输出

1

说明

用户状态依次为 R, R, F, R, F。好友关系构成一条链 $1-2-3-4-5$。相邻且状态相同的用户进行合并：$1$ 和 $2$ 均为 R，合并为一个大小 $2$ 的分组；$3$ 为 F，单独一组；$4$ 为 R，单独一组；$5$ 为 F，单独一组。根据题解代码逻辑，只统计状态为 R 的分组，得到大小列表 $[2, 1]$。升序排序后为 $[1, 2]$，第 $k=2$ 大的元素为 $1$，故输出 1。

样例2

输入

4 3
RFRF
1 2
2 3
3 4

输出

-1

说明

用户状态为 R, F, R, F，相邻用户状态均不同，因此每个用户都是一个独立的分组。其中状态为 R 的分组有 $2$ 个（大小均为 $1$）。同状态分组的数量 $2$ 小于 $k=3$，根据题意输出 $-1$。

样例3

输入

1 1
R

输出

1

说明

网络中只有 $1$ 个用户，状态为 R。该用户单独构成一个大小为 $1$ 的同状态分组。分组数量为 $1$，$k=1$ 时第 $1$ 大的分组大小即为 $1$。