T195763 【生物】分类

小峰在做一道关于生物分类的题目，题目中将一些生物进行了分类，形成如下图所示的结构：  小峰数了数，分类图中一共有 $n$ 个方框，构成了一棵树。他把这些方框命名为 $1$ 到 $n$，顶端方框编号为 $1$。然后这张图中了膜法，方框中出现了数，图中出现了一些原来没有的边，每条边也都带着一个数。 小峰数了一下，算上原来就有的边，一共有 $r$ 条。 这下子小峰没法做题了，为了做题，他必须还原出这个图来。 小峰记得原图是这个图的最小生成树。 现在，小峰需要破译解除膜法的密码。膜法会对该图进行 $m$ 次操作。操作分为 $6$ 种： - `1 x` 整个图的顶端节点变成 $x$ 号方框。 - `2 x y p` 整个图中从 $x$ 到 $y$ 的方框上面的数会被加上 $p$。即从 $x$ 到 $y$ 的简单路径上的所有数的值都会加上 $p$。 - `3 x p` 所有属于 $x$（包括 $x$）的方框上面的数会被加上 $p$，即 $x$ 的子树会被全部加上 $p$。 - `4 x y` 你需要求出 $x$ 和 $y$ 同属的种类的最小种类的方框上面的数。即 $x$ 与 $y$ 的 LCA 节点的值。 - `5 x y` 你需要求出 $x$ 到 $y$ 之间所有方框上面的数的和，即求 $x$ 到 $y$ 的简单路径上所有点的和。 - `6 x` 你需要求出所有属于方框 $x$（包括 $x$）的方框上面的数的和，即 $x$ 的子树的数的和。 如果膜法进行的操作是 $4,5,6$，则小峰需要对膜法的询问进行回答。否则，他将无法做出这道题目。 时间紧迫，小峰还要检查前面的题目，你能帮他算出答案吗？ **如果最小生成树不唯一，请输入顺序靠前的边优先级更高。**

第一行三个整数 $n,m,r$，表示方框数量、操作个数、边的总数。 第二行，$n$ 个整数，第 $i$ 个数表示编号为 $i$ 的方框上一开始写的数 $a_i$。 第三行到第 $r+2$ 行，每行三个整数 $x,y,w$，表示一条边连接 $x,y$，长度为 $w$。 第 $r+3$ 行到第 $r+m+2$ 行，每行一个操作，格式如上所述。

对于操作 $4,5,6$，输出一行一个整数表示密码（答案）。

#### 样例解释 #1 原图：  - 执行操作一后三个方框的数都是 $2$。 - $2$ 与 $3$ 的 $LCA$ 是 $1$，方框 $1$ 上面的数是 $2$。 - 将顶端节点换为 $3$，整棵树变成：  - 查询 $2$ 到 $3$ 路径上数的和，就是整棵树的结点的数字和，为 $2+2+2=6$。 - 给 $1$ 的子树加上 $1$，方框 $1,2,3$ 上面的数分别是：$3,3,2$。 - 查询 $3$ 的子树，即整棵树的数字和，为 $3+3+2=8$。 ------- #### 数据范围 对于 $5\%$ 的数据： $n=m=1$。 对于 $50\%$ 的数据：$1\le n,m\leq 10^4$。 对于 $100\%$ 的数据：$1\le n,m\leq 3\times 10^5$，$1\le a,r\leq 5\times 10^5$，$1\le w\leq 10^9$。 大样例： ```cpp 链接：https://pan.baidu.com/s/13S_ruD4iK8BU7OCx8uBYcA 提取码：2oz3 复制这段内容后打开百度网盘手机App，操作更方便哦 链接：https://pan.baidu.com/s/1XLtW8mXiHvV2d-ES2wPosg 提取码：gqqz 复制这段内容后打开百度网盘手机App，操作更方便哦 ```