day4测试题解

T1

如果 $i$ 是一个联通块的 祖先那么就把它砸破，这样整个联通块就都可以取出。

因此本题就是求出有多少个连通块，即统计有多少个点 $i$ 满足：

• find(i) == i

---

T2

由于每个数字 $A_i$ 不是 $1$ 就是 $2$。

因此知道 $A_{X_i}$ 则必然可以算出 $A_{Y_i}$。

根据题目的 $m$ 条关系可以维护出若干个连通块，显然一个连通块内的点只要知道一个值就可以推出其他所有的。

因此代码和第一题一样也是维护有几个连通块。

---

T3

对边权升序排序后，每加入一条边，边权记为 $w$，考虑图是树，所以必然会联通两个联通块。

而对于两个联通块内，我们使一个联通块联通的边，没有比当前边更大的边，因为边权已经升序排序了。

那么这两个联通块，一个联通块内的点到另一个联通块的点的路径上的最大边的边权就是 $w$。

有多少对 $f(i,j)$ 呢？设两个联通块的大小分别为 $size_u$ 和 $size_v$，共有 $size_u\times size_v$ 个点对。

• 这就是 $w$ 这条边的贡献。

sort(e, e + n, cmp); // 边权排序
for (int i = 0; i < n; i++)
{
    int u = e[i].u, v = e[i].v, w = e[i].w;
    u = find(u), v = find(v);
    if (u != v)
    {
        res += 1ll * w * sz[u] * sz[v];
        fa[u] = v, sz[v] += sz[u];
    }
}
cout << res;

---

T4

种类并查集

使用 $1\sim n$ 维护正电子的集合，$n+1\sim 2n$ 维护负电子的集合。

操作一：

• 合并 $(a,b+n)$ 以及 $(b,a+n)$。表示 $a,b$ 互相吸引。
  • 若 $a$ 是正电子，则 $b$ 就是负电子。反之亦然。

操作二：

• 合并 $(a,b)$ 以及 $(b+n,a+n)$。
  • 若 $a$ 是正电子，则 $b$ 就是正电子。反之亦然。

操作三：

• 若 find(x) == find(y + n)，则互相吸引。输出 A。
• 若 find(x) == find(y)，则互相排斥。输出 B。
• 否则输出 ?。

实现时注意空间大小。