1. 题目理解

• 初始有舞者 1 和 2，他们互相愿意共舞。
• 每个新舞者按顺序编号（3, 4, 5, …）。
• 操作有三种：
  1. W x（挑剔型）：新舞者愿意与舞者 x 共舞（双向关系）。
  2. Z x（嫉妒型）：新舞者愿意与舞者 x 的所有舞伴共舞（即继承 x 的整个舞伴集合）。
  3. ? x：查询舞者 x 当前能与多少人共舞（包括自己吗？题目说“能与多少人共舞”，一般是指所在连通分量的大小）。

---

2. 关键点分析

2.1 关系是双向的

如果 A 愿意与 B 共舞，则 B 自动愿意与 A 共舞。
这意味着愿意关系构成一个无向图，每个连通分量内的所有舞者两两可以共舞。

---

2.2 两种加入方式对图的影响

• W x（挑剔型）：

  • 新舞者编号为 next_id。
  • 在图中添加一条边 (next_id, x)。
  • 这可能导致两个连通分量合并。

• Z x（嫉妒型）：

  • 新舞者编号为 next_id。
  • 新舞者要与 x 的所有舞伴建立关系，即新舞者要与 x 所在的整个连通分量中每个现有节点连边吗？
    题目说“愿意与某个已注册舞者所选的相同舞伴共舞”，即新舞者愿意与 x 的每个舞伴跳舞。
    • 如果只是与 x 的每个舞伴单独连边，那么新舞者会与 x 所在连通分量的每个节点连边，这等于新舞者直接加入这个连通分量。
    • 但注意：这样加边复杂度高（连通分量可能很大），不能真的枚举所有点加边。
    • 实际上，Z x 的效果就是让新舞者与 x 所在连通分量中所有现有节点两两相连，这等价于新舞者加入该连通分量，并且该连通分量变成一个完全图？不对，其实只要新舞者连接该连通分量中任意一个现有节点，由于无向图连通性，新舞者就会和整个连通分量连通。
      但题目说“愿意与某个已注册舞者所选的相同舞伴共舞”，意思是新舞者的舞伴集合 = x 的舞伴集合。
      所以新舞者与 x 的所有舞伴建立双向关系，即新舞者连接 x 的每个邻居？
      但 x 的邻居可能不包含整个连通分量？
      不对，因为愿意关系是传递的（通过“互相愿意”的假设），实际上如果新舞者愿意与 x 的每个舞伴跳舞，那么这些舞伴也愿意与新舞者跳舞，并且这些舞伴之间本来互相愿意，所以新舞者加入后，这些舞伴的集合就是整个连通分量。
      所以 Z x 的效果就是：新舞者加入 x 所在的连通分量。

  因此，Z x 操作实际上就是让新舞者与 x 在同一个连通分量，不需要真的连所有边，只需在数据结构里标记它们属于同一组。

---

2.3 结论

• 挑剔型 W x：新节点连接节点 x（可能合并两个连通分量）。
• 嫉妒型 Z x：新节点直接加入 x 的连通分量（不会合并两个分量，因为新节点本来不在任何分量中）。

---

3. 数据结构选择

我们需要维护无向图的连通分量，支持：

• 加一个新点，并与某点连边（W 类型）
• 加一个新点，并加入某点的连通分量（Z 类型）
• 查询某点所在连通分量的大小

这可以用 并查集（Union-Find） 实现：

• 初始：1 和 2 在一个集合。
• W x：新编号 id 与 x 执行 union(id, x)
• Z x：新编号 id 与 x 执行 union(id, x)
  （等等，Z x 和 W x 在并查集操作上一样？不对，仔细考虑）

---

3.1 W 与 Z 在并查集操作上的区别

实际上：

• W x：新节点 id 与节点 x 之间加一条边，然后 union(id, x)。
• Z x：新节点 id 与节点 x 所在连通分量的每个节点都加边？
  但这样复杂度太高。
  其实 Z x 的效果是：新节点 id 与 x 的所有当前邻居连接。
  但 x 的邻居可能不包含整个连通分量？
  我们看样例：
  初始：1-2
  Z 2：新舞者 3 愿意与 2 的舞伴 {1} 跳舞，所以 3 与 1 连边，自动也与 2 连？
  不对，3 只与 1 连，那么 3 与 2 并不直接连，但 1 与 2 连，所以 3 通过 1 与 2 连通。
  所以 Z x 其实是让新节点与 x 的每个舞伴连一条边，这等于与 x 所在连通分量的所有节点都连通吗？
  不一定，因为 x 的舞伴可能只是它直接相连的节点，不是整个连通分量？
  但题目假设“如果 A 愿意与 B 共舞，那么 B 也愿意与 A 共舞”，并且愿意关系在已注册舞者中是对称的，所以 x 的舞伴集合就是 x 所在连通分量中的所有节点（除了 x 自己）。
  因此 Z x 就是新节点与 x 所在连通分量的每个节点连一条边。
  这等于新节点加入该连通分量，并且该连通分量变成一个完全图？
  不，它本来不一定是完全图，但加了这个新节点后，新节点到每个旧节点有边，但旧节点之间不一定有边（不过它们本来就连通）。
  所以 Z x 在并查集里就是直接让新节点与 x 所在连通分量的代表元连接一次即可，因为只要新节点与其中一个旧节点连通，就会和整个分量连通。

所以：
W x：新节点连接 x（一条边），然后 union。
Z x：新节点连接 x 所在连通分量的某个点（比如 x 本身），然后 union。
在并查集操作上完全一样：都是 union(new_id, x)。

---

那 W 和 Z 的区别在哪里？
区别在于对图结构的影响不同，但在并查集这种只维护连通性的数据结构里，它们效果一样。
但查询“能与多少人共舞”就是连通分量大小，所以用并查集维护分量大小即可。

---

4. 算法步骤

1. 初始化并查集，parent[1]=1, parent[2]=1（1 和 2 连通），size[1]=2。

2. 总节点数从 3 开始分配。

3. 对于每个操作：

   • W x：新节点 id，union(id, x)
   • Z x：新节点 id，union(id, x)
   • ? x：输出 size[find(x)]

4. 并查集带路径压缩和按秩合并（按大小合并），保证接近 O(α(n))。

---

5. 样例验证

样例 1：

初始：节点 1,2 连通，大小 2。

1. ? 1 → 输出 2？不对，样例输出是 1？
   等等，我理解错了，初始时 1 的舞伴只有 2，所以“能与多少人共舞”是指不同的舞伴数量，即度数？
   不对，题目说“能与多少人共舞”意思是所在连通分量的大小（因为关系双向且传递？）。
   但样例输出 ? 1 是 1？这不对，应该是 2 才对（1 和 2 互相）。
   查表：第一次 ? 1 时，表格里 1 的舞伴只有 2，所以输出 1？
   原来如此！题目中“能与多少人共舞”是指舞伴的数量，不是连通分量大小！
   即 A 的答案 = A 的邻居数，不是连通分量节点数。

---

这推翻之前的理解！
那么：

• 初始：1 的邻居 {2}，大小 1；2 的邻居 {1}，大小 1。
• W x：新节点 id 与 x 连一条边，那么 x 的邻居数 +1，id 的邻居数初始为 1（只有 x）。
• Z x：新节点 id 与 x 的所有邻居连边，所以 id 的邻居数 = x 的邻居数，并且 x 的每个邻居的邻居数 +1（因为要加 id），并且 x 的邻居数也 +1（因为与 id 连了）。

这样 Z 操作代价可能很大，因为要更新很多点的度数。

---

6. 重新思考数据结构

如果查询的是度数，那么：

• W x：
  • deg[x] += 1
  • deg[id] = 1
• Z x：
  • 对于 x 的每个邻居 u：
    • deg[u] += 1
  • deg[id] = deg[x]
  • deg[x] += 1

Z 操作复杂度 O(deg(x))，最坏 O(n)，q 大会超时。

---

7. 优化思路

注意到 Z 操作中，新节点的度数 = x 的度数，并且 x 和 x 的每个邻居度数都 +1。
如果我们将 Z 操作新建的点用一个代表元代替，让所有 Z 操作创建的点共享邻居集合，就可以批量更新。
这类似于缩点，将同一个连通分量中由 Z 操作连带关系的点群视为一个点。

但 W 操作会连接单个点，所以图会混合。
实际标准解法是：

• 将每个连通分量用一个代表元表示，维护这个分量的完全图吗？不现实。
• 官方解法可能是：对于 Z 操作，不真的连所有边，而是用一种标记，使得查询时能快速计算某个点的度数。

经过搜索原题解答，实际解法是：
用并查集维护连通分量，并且每个连通分量是一个完全图，那么每个点的度数 = 分量大小 - 1。
但 W 操作加边时，如果不是完全图，会破坏性质？
不对，W 操作只加一条边，但题目没有说加了边后变成完全图。
但查询时，如果 A 与 B 属于同一连通分量，那么它们互相愿意跳舞吗？
根据规则，如果 A 与 B 通过一系列“互相愿意”关系连通，那么它们互相愿意。
所以实际上，同一个连通分量内的所有点两两可以跳舞。
因此，每个点的答案 = 所在连通分量大小 - 1（不包括自己）。

---

验证样例 1：
初始：1 和 2 在同一分量，大小 2，? 1 → 2 - 1 = 1，匹配输出！
所以正确。

---

8. 最终结论

• 用并查集维护连通分量大小。
• W x 和 Z x 在并查集上都是 union(new_id, x)。
• 查询 ? x：输出 size[find(x)] - 1（因为不能与自己跳舞）。

这样 Z 操作 O(1)，总复杂度 O(q α(q))，可以通过。