P3979 遥远的国度

`zcwwzdjn` 在追杀 `zhx` ，而 `zhx` 逃入了一个遥远的国度。当 `zcwwzdjn` 准备进入遥远的国度继续追杀时，守护神 `RapiD` 阻拦了 `zcwwzdjn` 的去路，他需要 `zcwwzdjn` 完成任务后才能进入遥远的国度继续追杀。 问题是这样的：遥远的国度有 $n$ 个城市，这些城市之间由一些路连接且这些城市构成了一颗树。这个国度有一个首都，我们可以把这个首都看做整棵树的根，但遥远的国度比较奇怪，首都是随时有可能变为另外一个城市的。遥远的国度的每个城市有一个防御值，第 $i$ 个的防御值为 $val_i$，有些时候 `RapiD` 会使得某两个城市之间的路径上的所有城市的防御值都变为某个值。 `RapiD` 想知道在某个时候，如果把首都看做整棵树的根的话，那么以某个城市为根的子树的所有城市的防御值最小是多少。 由于 `RapiD` 无法解决这个问题，所以他拦住了 `zcwwzdjn` 希望他能帮忙。但 `zcwwzdjn` 还要追杀 `zhx`，所以这个重大的问题就被转交到了你的手上。

无

无

对于 $20\%$ 的数据，$n\le 1000,m\le 1000$。 对于另外 $10\%$ 的数据，$n\le 100000,m\le 100000$，保证修改为单点修改。 对于另外 $10\%$ 的数据，$n\le100000,m \le 100000$，保证树为一条链。 对于另外 $10\%$ 的数据，$n\le 100000,m\le100000$，没有修改首都的操作。 对于 $100\%$ 的数据，$1 \leq n\le 100000,1 \leq m \le 100000,0