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

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

题目描述

请注意本题不同寻常的空间限制。

给定 操作序列 AA 和一棵有根树 TTAA 中的每个操作都形如「给 TTuuvv 的简单路径上的所有点权增加 xx」。其中,uuvv 的简单路径定义为:从 uu 开始到 vv 结束的一条不重复访问任何节点和边的路径。

初始时 TT 的根为 11,所有点权皆为 00

你需要执行三种操作:

  • 给定区间 [l,r][l,r],依次执行 Al,Al+1A_l, A_{l+1}\dotsArA_r 的操作;
  • 查询 TTxx 为根的子树和;
  • TT 的根到 yy(若当前根为 yy,则不进行操作)。

输入格式

第一行包含三个正整数 n1n_1, n2n_2mm (1n1,n2,m1×1051\le n_1,n_2,m \le 1\times 10^5),用一个空格分隔,分别表示 AA 的长度、TT 的总点数、询问与操作的次数。

接下来 n1n_1 行,第 ii 行包含三个整数 uiu_i, viv_ixix_i (1ui,vin2,1xi1×1021\le u_i,v_i\le n_2, 1\le x_i\le 1\times 10^2),用一个空格分隔,表示操作 AiA_i 为「给 TTuiu_iviv_i 的简单路径上的所有点权增加 xix_i」。

接下来 n21n_2-1 行,每行包含两个正整数 uuvv (1u,vn21\le u,v \le n_2),用一个空格分隔,表示树的一条边。保证该 n21n_2-1 条边构成树。

接下来 mm 行,每行的第一个数 opop (op{1,2,3}op\in \{1,2,3\}) 表示操作编号,随后:

  • opop11,则后面跟随两个正整数 llrr (1lrn11\le l\le r\le n_1),用一个空格分隔,表示依次执行 Al,Al+1ArA_l, A_{l+1} \dots A_r 的操作;
  • opop22,则后面跟随一个正整数 xx (1xn21\le x\le n_2),表示查询 TTxx 为根的子树和;
  • opop33,则后面跟随一个正整数 yy (1yn21\le y\le n_2),表示换 TT 的根到 yy(若当前根为 yy,则不进行操作)。

输出格式

对于每个操作 22,输出一行一个整数,表示 TTxx 为根的子树和。

数据保证答案在有符号超长整型所表达的范围内。

4 5 7
3 5 2
5 4 3
3 1 2
2 5 1
2 1
4 2
1 5
3 2
1 1 4
2 1
1 2 3
2 2
3 3
1 1 3
2 2
29
25
63