P8123 [BalticOI 2021] Inside information (Day1)
题目描述
有 $N$ 个服务器,第 $i$ 个服务器存储着第 $i$ 块数据,现在有若干种操作:
- `S a b` 第 $a$ 个服务器与第 $b$ 个服务器共享数据,即这两个服务器同时拥有这两个服务器本身拥有的数据块的和,并自动去重(可以理解为数据块之并)。
- `Q a d` 查询第 $a$ 个服务器是否拥有第 $d$ 块数据。
- `C a` 查询存储数据块 $a$ 的服务器数量。
S 操作有 $N-1$ 次,如果把共享看做连边,那么最后将形成以 $N$ 个服务器为点的一棵树;Q 操作和 C 操作一共有 $K$ 次。
求对于每个 Q 操作和 C 操作返回的结果。
输入格式
第一行两个整数 $N,K$ 代表服务器个数和操作个数。
接下来 $N+K-1$ 行每行代表一个操作。
输出格式
$K$ 行:
- 对于 Q 操作,输出 `yes` 或 `no` 代表是否拥有第 $d$ 块数据;
- 对于 C 操作,输出一个整数代表服务器数量。
说明/提示
#### 数据规模与约定
**本题采用捆绑测试。**
- Subtask 1(5 pts):$N \le 4000$。
- Subtask 2(5 pts):第 $1$ 个服务器与第 $2,3,\cdots,N$ 个服务器共享数据。
- Subtask 3(10 pts):如果 $|A-B|=1$,那么第 $A$ 个服务器和第 $B$ 个服务器共享数据。
- Subtask 4(20 pts):如果 $A