# 动态目录树

- 参考时间限制：**1.5 秒**（[评测环境与性能](../../../docs/评测环境与性能.md)）。
- 实际时限：在目标环境实测标准程序最慢测试文件的中位时间，乘以 2，再按 0.5 秒向上取整。
- 内存限制：**512 MB**。

## 背景故事

电脑店正在制作一份可调整的目录索引。目录之间的连接带有权值；技术员可以搬移整棵子目录、改变观察目录树的根，或者修改一条连接的权值。查询时，他关心从当前根出发前往若干目录的公共路段。

(本故事由GPT-6重写)

## 形式化问题描述

给定一棵含 $n$ 个节点的无向带权树，节点编号为 $1,\ldots,n$ ，初始根为节点 $1$ .边权可以为负。

依次执行以下操作。所有父子关系和子树都按**操作执行前的当前根**确定。

1. `1 a b v` ：将以 $a$ 为根的整棵子树移动到 $b$ 下面。若 $b$ 在该子树内，包括 $a=b$ ，忽略操作；否则删除 $a$ 与其父亲之间的边，再连接 $a,b$ ，新边权为 $v$ .当前根不变。
2. `2 a` ：把当前根改为 $a$ ，无向边和边权不变。
3. `3 a b v` ：若 $a,b$ 之间存在直接相连的边，把其权值改为 $v$ ；否则忽略操作。
4. `4 k a1 a2 ... ak` ：分别考察从当前根到这 $k$ 个节点的简单路径。它们的公共部分是从根开始的一条路径，输出这条公共路径的**边权之和**。

当公共部分只有根节点时，答案为 $0$ ；其他情况下答案也可能为负数。以当前根为根的子树包含整棵树，因此对当前根执行操作 1 会被忽略。

## 输入格式

第一行两个整数 $n,m$ ，表示节点数和操作数。

接下来 $n-1$ 行，每行三个整数 $a,b,v$ ，表示一条无向边及其权值。

接下来 $m$ 行，每行一个操作，格式如上。

## 输出格式

对每个操作 4，按出现顺序输出一行整数。没有查询时不输出任何内容。

## 样例 1

### 输入

```text
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
```

### 输出

```text
8
10
2
3
7
2
11
7
17
17
11
10
```

## 样例 2

### 输入

```text
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
```

### 输出

```text
-4
1
0
```

## 样例 3

### 输入

```text
2 0
1 2 0
```

### 输出

```text

```

## 样例解释

样例 1 的首次双点查询询问节点 $5,6$ .两条路径共享 $1\to2\to3$ ，边权之和为 $2+5=7$ .

![样例1中通往节点5与6的路径共享从1到3的前缀](assets/common-prefix.svg)

粗线表示公共路径，边旁的数是边权。

样例 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% | 无额外条件 |