动态目录树¶
- 参考时间限制：1.5 秒（评测环境与性能）。
- 实际时限：在目标环境实测标准程序最慢测试文件的中位时间，乘以 2，再按 0.5 秒向上取整。
- 内存限制：512 MB。
背景故事¶
电脑店正在制作一份可调整的目录索引。目录之间的连接带有权值；技术员可以搬移整棵子目录、改变观察目录树的根，或者修改一条连接的权值。查询时，他关心从当前根出发前往若干目录的公共路段。
(本故事由GPT-6重写)
形式化问题描述¶
给定一棵含 \(n\) 个节点的无向带权树，节点编号为 \(1,\ldots,n\) ，初始根为节点 \(1\) .边权可以为负。
依次执行以下操作。所有父子关系和子树都按操作执行前的当前根确定。
1 a b v：将以 \(a\) 为根的整棵子树移动到 \(b\) 下面。若 \(b\) 在该子树内，包括 \(a=b\) ，忽略操作；否则删除 \(a\) 与其父亲之间的边，再连接 \(a,b\) ，新边权为 \(v\) .当前根不变。2 a：把当前根改为 \(a\) ，无向边和边权不变。3 a b v：若 \(a,b\) 之间存在直接相连的边，把其权值改为 \(v\) ；否则忽略操作。4 k a1 a2 ... ak：分别考察从当前根到这 \(k\) 个节点的简单路径。它们的公共部分是从根开始的一条路径，输出这条公共路径的边权之和。
当公共部分只有根节点时，答案为 \(0\) ；其他情况下答案也可能为负数。以当前根为根的子树包含整棵树，因此对当前根执行操作 1 会被忽略。
输入格式¶
第一行两个整数 \(n,m\) ，表示节点数和操作数。
接下来 \(n-1\) 行，每行三个整数 \(a,b,v\) ，表示一条无向边及其权值。
接下来 \(m\) 行，每行一个操作，格式如上。
输出格式¶
对每个操作 4，按出现顺序输出一行整数。没有查询时不输出任何内容。
样例 1¶
输入¶
7 16
1 2 2
2 3 5
2 4 6
3 5 1
3 6 3
4 7 -5
4 1 5
4 1 6
4 1 2
4 1 7
4 2 5 6
4 3 6 3 7
1 4 6 6
4 1 7
4 3 6 5 7
3 4 5 1
3 4 7 1
4 1 7
2 7
4 1 1
4 1 5
4 2 5 1
输出¶
8
10
2
3
7
2
11
7
17
17
11
10
样例 2¶
输入¶
3 8
1 2 -4
2 3 1
4 2 2 3
1 1 3 9
1 2 3 8
3 1 3 9
2 3
4 2 1 2
1 1 3 7
4 2 1 2
输出¶
-4
1
0
样例 3¶
输入¶
2 0
1 2 0
输出¶
样例解释¶
样例 1 的首次双点查询询问节点 \(5,6\) .两条路径共享 \(1\to2\to3\) ，边权之和为 \(2+5=7\) .
粗线表示公共路径，边旁的数是边权。
样例 2 的三个答案依次为 \(-4,1,0\) .其中两次把子树移入自身的操作，以及一次修改不存在边的操作，都被忽略。样例 3 没有操作，因此输出为空。
数据范围与保证¶
对 100% 的数据：\(2\le n\le200000\) ，\(0\le m\le200000\) ，所有初始及修改后的边权满足 \(|v|\le10000\) .节点编号均在 \(1,\ldots,n\) 内，初始边构成一棵树。
每次查询满足 \(1\le k\le200000\) ，查询节点互不相同；所有查询的 \(k\) 之和不超过 \(200000\) .
| 分值比例 | 额外条件 |
|---|---|
| 100% | 无额外条件 |