#P12536. [XJTUPC 2025] 我永远喜欢希儿·芙乐艾
[XJTUPC 2025] 我永远喜欢希儿·芙乐艾
题目描述
请注意本题不同寻常的空间限制。
给定 操作序列 和一棵有根树 , 中的每个操作都形如「给 中 到 的简单路径上的所有点权增加 」。其中, 到 的简单路径定义为:从 开始到 结束的一条不重复访问任何节点和边的路径。
初始时 的根为 ,所有点权皆为 。
你需要执行三种操作:
- 给定区间 ,依次执行 到 的操作;
- 查询 以 为根的子树和;
- 换 的根到 (若当前根为 ,则不进行操作)。
输入格式
第一行包含三个正整数 , 和 (),用一个空格分隔,分别表示 的长度、 的总点数、询问与操作的次数。
接下来 行,第 行包含三个整数 , 和 (),用一个空格分隔,表示操作 为「给 中 到 的简单路径上的所有点权增加 」。
接下来 行,每行包含两个正整数 和 (),用一个空格分隔,表示树的一条边。保证该 条边构成树。
接下来 行,每行的第一个数 () 表示操作编号,随后:
- 若 为 ,则后面跟随两个正整数 和 (),用一个空格分隔,表示依次执行 的操作;
- 若 为 ,则后面跟随一个正整数 (),表示查询 以 为根的子树和;
- 若 为 ,则后面跟随一个正整数 (),表示换 的根到 (若当前根为 ,则不进行操作)。
输出格式
对于每个操作 ,输出一行一个整数,表示 以 为根的子树和。
数据保证答案在有符号超长整型所表达的范围内。
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