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 自动生成