U598930 HS_fu3的语录

[MyShiroko](https://www.luogu.com.cn/user/1642068) 一直暗恋 [HS_fu3](https://www.luogu.com.cn/user/1631373)，甚至记下了 HS_fu3 对他说过的每一句话。[见此处](https://www.cnblogs.com/MyShiroko/p/19038330)\ 这些话互相可能会产生一些关系而形成语录，语录之间也可能合并，但总有其中一些重要的话占局部的主导地位，形象的来说，这些话语构成了多个并查集，并查集会合并，而重要的话就是某些并查集的根！ 众所周知，路径压缩是一个很好的实现并查集快速查询的方法，但是有人不会。 MyShiroko 经常想要查询这些重要的话，但是他只能从语录的某些话查起，直到找到那句重要的话，观看这些话语是有代价的（看多了绝对会变奇怪的！），MyShiroko 想知道某些话所在的语录的重要的话以及观看重要的话需要付出的代价，你需要帮助他回答。 不仅如此，MyShiroko 记录的语录太多了！！！他有时候会想要整合两个不同的语句所在的语录，这时他会让这两个语录重要的话相互连接，具体地说，合并两个语录时，前一个的重要的话会成为新的重要的话，正如刚才所说，他在查找这些重要的话时会付出代价，他同样想知道这个，你也要回答。

现给出 $n$ 个点，第 $i$ 个点的权值为 $a_i$，初始时每个点都是一棵有根树。 定义操作 $find\ x$，找到 $x$ 所在有根树的根。这次操作的代价是 $x$ 到根的路径上所有点的点权和。 定义操作 $merge\ x\ y$ - 首先找到 $x$，$y$ 所在有根树的根，记 $x' = find\ x$，$y' = find\ y$。 - 若 $x ′ = y ′$，将 $y ′$ 的父亲设为 $x ′$。这意味着 $x ′$，$y ′$ 这两棵有根树合并到一起，以后 $find\ y$ 和 $find\ x$ 应该相等。 定义操作 $change\ x\ y$，将第 $x$ 个点的权值更改为 $y$。 给出总共 $m$ 次 $merge$、$find$ 和 $change$ 操作，对于每一个 $merge$ 操作，回答 $find\ x$ 与 $find\ y$ 的代价和，对于每一个 $find$ 操作，回答树根和代价。 **注意**：数据不保证最终一定是一棵树。

第一行两个整数 $n$，$m$，代表点的个数和操作个数。 第二行一行 $n$ 个整数 $a_1 \dots a_n$，代表每个点的权值。 之后 $m$ 行，每行一个字母 $opt$， - 若为$f$ 代表 $find$ 操作。之后跟着一个整数 $x$，含义如上。 - 若为$m$ 代表 $merge$ 操作。之后跟着两个整数 $x$，$y$，含义如上。 - 若为$c$ 代表 $change$ 操作。之后跟着两个整数 $x$，$y$，含义如上。

对于操作 $find$，输出一行两个整数，含义如上。 对于操作 $merge$，输出一行一个整数，含义如上。

## tips:数据已加强 对于 $20\%$ 的数据，保证 $1 \le n,m \le 2 \times 10^3$。 对于另外 $30\%$ 的数据，保证不存在 $change$ 操作。 对于 $100\%$ 的数据，$1 \le n,m \le 2 \times 10^5$。 | data | std | | ----------- | ----------- | | [lyms_Hz17](https://www.luogu.com.cn/user/1598011) | [MyShiroko](https://www.luogu.com.cn/user/1642068) |