AT_tkppc2016_j 次のお仕事 (New Game)
题目描述
joisino 姐姐完成了一个游戏后，决定开始策划下一个游戏。这次，她打算设计一个地形会变化的冒险游戏。游戏中有以下设定：
在这个游戏中，有 $N$ 个城镇，通过 $N-1$ 条双向道路相互连接，形成了一个连通的地图。玩家需要在这些城镇间旅行以到达目标。不过，你只需要考虑最短路径。由于地形的变化，海拔成为了一个重要因素。穿越高海拔的城镇可能会获得稀有物品，因此找出旅途中经过城镇的最高海拔是至关重要的。此外，可以通过改变化拔来改变特定区域的地形。
具体来说，游戏中会发生以下两种事件：
- **事件 1**
给定整数 $a, b, c$。将从城镇 $a$ 出发，沿不超过 $b$ 条边能到达的所有城镇的海拔统一设为 $c$。
- **事件 2**
给定整数 $a, b$。计算出从城镇 $a$ 到达城镇 $b$ 的最短路径上的城镇中最高的海拔，根据最高海拔领取相应的奖励。
这样做可以获得哪些物品呢？为了探求这个问题，joisino 姐姐决定编写一个程序，专门用来求出在事件 2 中，最短路径上城镇海拔的最大值。
### 输入格式
输入无特殊格式要求。
### 输出格式
对于每一次事件 2，输出从城镇 $a$ 到城镇 $b$ 的最短路径上，所有经过城镇中的最大海拔值。
### 输入示例 1
```
5 5
3
2
5
2
6
1 2
2 3
3 5
3 4
2 1 5 0
1 4 1 7
2 5 2 0
1 3 1 2
2 4 1 0
```
### 输出示例 1
```
6
7
3
```
- **查询 1**：从城镇 $1$ 到达城镇 $5$ 的最短路径是 $1 \to 2 \to 3 \to 5$，经过城镇海拔分别为 $3,\ 2,\ 5,\ 6$，最大值为 $6$。
- **查询 2**：将从城镇 $4$ 出发，沿一条边能够到达的城镇 $4$ 和 $3$ 的海拔设为 $7$。
- **查询 3**：从城镇 $5$ 到城镇 $2$ 的最短路径是 $5 \to 3 \to 2$，经过城镇海拔分别为 $6,\ 7,\ 2$，最大值为 $7$。
- **查询 4**：将从城镇 $3$ 出发，沿一条边能够到达的城镇 $3,\ 2,\ 4,\ 5$ 的海拔设为 $2$。
- **查询 5**：从城镇 $4$ 到城镇 $1$ 的最短路径是 $4 \to 3 \to 2 \to 1$，经过城镇海拔分别为 $2,\ 2,\ 2,\ 3$，最大值为 $3$。
### 输入示例 2
```
10 10
78
87
33
57
93
49
45
17
56
44
1 2
2 3
1 4
1 5
4 6
3 7
6 8
3 9
6 10
2 2 2 0
1 1 2 59
1 7 1 96
2 7 8 0
2 3 4 0
2 10 4 0
1 8 2 45
1 3 3 24
2 2 1 0
2 6 9 0
```
### 输出示例 2
```
87
96
96
59
24
45
```
该问题测试在城镇连接形成的树结构内处理路径查询与更新问题，是对图算法的应用与挑战。
**本翻译由 AI 自动生成**
输入格式
无
输出格式
すべてのイベント2について、最短経路の街の標高の最大値を出力せよ。
- - - - - -
### 入力例1
```
5 5
3
2
5
2
6
1 2
2 3
3 5
3 4
2 1 5 0
1 4 1 7
2 5 2 0
1 3 1 2
2 4 1 0
```
### 出力例1
```
6
7
3
```
- クエリ$ 1 $ : 街$ 1 $から街$ 5 $までの最短経路で通る街は$ 1,\ 2,\ 3,\ 5 $なので、それらの標高$ 3,\ 2,\ 5,\ 6 $の最大値$ 6 $を出力する。
- クエリ$ 2 $ : 街$ 4 $から$ 1 $本の道を通ってたどり着ける街は$ 4,\ 3 $なので、それらの標高を$ 7 $にする。
- クエリ$ 3 $ : 街$ 5 $から街$ 2 $までの最短経路で通る街は$ 5,\ 3,\ 2 $なので、それらの標高$ 6,\ 7,\ 2 $の最大値$ 7 $を出力する。
- クエリ$ 4 $ : 街$ 3 $から$ 1 $本の道を通ってたどり着ける街は$ 3,\ 2,\ 4,\ 5 $なので、それらの標高を$ 2 $にする。
- クエリ$ 5 $ : 街$ 4 $から街$ 1 $までの最短経路で通る街は$ 4,\ 3,\ 2,\ 1 $なので、それらの標高$ 2,\ 2,\ 2,\ 3 $の最大値$ 3 $を出力する。
- - - - - -
### 入力例2
```
10 10
78
87
33
57
93
49
45
17
56
44
1 2
2 3
1 4
1 5
4 6
3 7
6 8
3 9
6 10
2 2 2 0
1 1 2 59
1 7 1 96
2 7 8 0
2 3 4 0
2 10 4 0
1 8 2 45
1 3 3 24
2 2 1 0
2 6 9 0
```
### 出力例2
```
87
96
96
59
24
45
```