笃志以砺，决起而飞

最近刷题得进度可以说慢到一定境界上了，今天中午抽空终于把n天前残留的 1703 给过掉了。 这个题目也是一个并查集的题目。但是在这道题目中，有一个非常重要的性质：

一个人不是属于集合 A，就是属于集合 B。

这样，假设 A、B 两个人不是在同一个 gang 中，A、C 两个人不是在同一个 gang 中，就必定有 B、C 两个人在同一个 gang 中。因此我们可以放心地将 B、C 两个人合并。

也就是说，每次发现 X Y 在不同的集合中，我们都可以将与 X 不在同一集合的与 Y 合并，将与 Y 不在同一集合的与 X 合并。根据并查集的性质，为了在每次合并时找到与其不在一个集合的元素，我们只需要记录他们的一个代表元素即可，于是我们使用 opt[x] 代表一个与 x 不在同一个集合的元素。

另外，本题读入必须使用 scanf，因为即使取消同步，cin 也会超时。

?View Code CPP1 2 3 4 5 6 7 8 9 10 11 12 13 [...]

这道题是一道并查集的题目。和普通并查集相比，主要有几点需要注意： 1、注意空树的处理。 2、如果在合并的时候，这两个点已经在树中，说明路径重复，不是合法的树。

?View Code CPP1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 [...]

虽然这道题使用 double 类型就可以过，但我由于担心精度问题还是写了高精度。 实际上，由于一个数被乘方之后很小的差别对应的结果差别非常大，所以 double 应该确实可以。

?View Code CPP1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 [...]