CF757G Can Bash Save the Day?

哇！你帮了火箭队的大忙，他们成功地捕获了 Bash 派出的所有宝可梦。Meowth 作为火箭队的一员，已经精通了人类语言，现在还想成为编程大师。他同意只要 Bash 能回答他的问题，就释放这些宝可梦。 最初，Meowth 给 Bash 一棵有 $n$ 个结点的加权树，以及一个长度为 $n$ 的序列 $a_1,a_2,...,a_n$，其中 $a$ 是 $1,2,...,n$ 的一个排列。之后，Meowth 进行 $q$ 个操作，每次操作为以下两种之一： - 1 l r v：让 Bash 汇报如下结果： $$ \sum_{i=l}^{r} dist(a_i, v) $$ 其中 $dist(a,b)$ 表示在给定树上从结点 $a$ 到结点 $b$ 的最短路径长度。 - 2 x：让 Bash 交换序列 $a$ 中位置 $x$ 和 $x+1$ 的元素。之后的所有查询都使用更新后的序列。 请你帮助 Bash 回答这些问题！

第一行包含两个整数 $n$ 和 $q$（$1\leq n\leq 2\times 10^5$，$1\leq q\leq 2\times 10^5$），分别表示树中结点的数量和操作数。 第二行包含 $n$ 个用空格分隔的整数，表示序列 $a_1,a_2,...,a_n$，是 $1,2,...,n$ 的一个排列。 接下来的 $n-1$ 行，每行包含三个用空格分隔的整数 $u$、$v$ 和 $w$，表示存在一条权值为 $w$ 的无向边，连接 $u$ 号点和 $v$ 号点（$1\leq u,v\leq n$，$u\ne v$，$1\leq w\leq 10^6$）。保证给定的图是一棵树。 每个操作包含两行。 第一行是一个整数 $t$，表示操作的类型。 第二行描述本次操作： - 如果 $t=1$，第二行包含三个整数 $a$，$b$ 和 $c$（$1\leq a,b,c

对于每一个 $1$ 型操作，输出一行一个整数，表示查询的答案。

样例中实际的操作如下： - 1 1 5 4 - 1 1 3 3 - 2 3 - 2 2 - 1 1 3 3 由 ChatGPT 5 翻译