P12536 [XJTUPC 2025] 我永远喜欢希儿·芙乐艾

**请注意本题不同寻常的空间限制。** 给定 **操作序列** $A$ 和一棵有根树 $T$，$A$ 中的每个操作都形如「给 $T$ 中 $u$ 到 $v$ 的简单路径上的所有点权增加 $x$」。其中，$u$ 到 $v$ 的简单路径定义为：从 $u$ 开始到 $v$ 结束的一条不重复访问任何节点和边的路径。 初始时 $T$ 的根为 $1$，所有点权皆为 $0$。 你需要执行三种操作： - 给定区间 $[l,r]$，依次执行 $A_l, A_{l+1}\dots$ 到 $A_r$ 的操作； - 查询 $T$ 以 $x$ 为根的子树和； - 换 $T$ 的根到 $y$（若当前根为 $y$，则不进行操作）。

第一行包含三个正整数 $n_1$, $n_2$ 和 $m$ ($1\le n_1,n_2,m \le 1\times 10^5$)，用一个空格分隔，分别表示 $A$ 的长度、$T$ 的总点数、询问与操作的次数。 接下来 $n_1$ 行，第 $i$ 行包含三个整数 $u_i$, $v_i$ 和 $x_i$ ($1\le u_i,v_i\le n_2, 1\le x_i\le 1\times 10^2$)，用一个空格分隔，表示操作 $A_i$ 为「给 $T$ 中 $u_i$ 到 $v_i$ 的简单路径上的所有点权增加 $x_i$」。 接下来 $n_2-1$ 行，每行包含两个正整数 $u$ 和 $v$ ($1\le u,v \le n_2$)，用一个空格分隔，表示树的一条边。保证该 $n_2-1$ 条边构成树。 接下来 $m$ 行，每行的第一个数 $op$ ($op\in \{1,2,3\}$) 表示操作编号，随后： - 若 $op$ 为 $1$，则后面跟随两个正整数 $l$ 和 $r$ ($1\le l\le r\le n_1$)，用一个空格分隔，表示依次执行 $A_l, A_{l+1} \dots A_r$ 的操作； - 若 $op$ 为 $2$，则后面跟随一个正整数 $x$ ($1\le x\le n_2$)，表示查询 $T$ 以 $x$ 为根的子树和； - 若 $op$ 为 $3$，则后面跟随一个正整数 $y$ ($1\le y\le n_2$)，表示换 $T$ 的根到 $y$（若当前根为 $y$，则不进行操作）。

对于每个操作 $2$，输出一行一个整数，表示 $T$ 以 $x$ 为根的子树和。 数据保证答案在有符号超长整型所表达的范围内。