P4175 [CTSC2008] 网络管理

M 公司是一个非常庞大的跨国公司，在许多国家都设有它的下属分支机构或部门。为了让分布在世界各地的 $n$ 个部门之间协同工作，公司搭建了一个连接整个公司的通信网络。 该网络的结构由 $n$ 个路由器和 $n-1$ 条高速光缆组成。每个部门都有一个专属的路由器，部门局域网内的所有机器都联向这个路由器，然后再通过这个通信子网与其他部门进行通信联络。该网络结构保证网络中的任意两个路由器之间都存在一条直接或间接路径以进行通信。 高速光缆的数据传输速度非常快，以至于利用光缆传输的延迟时间可以忽略。但是由于路由器老化，在这些路由器上进行数据交换会带来很大的延迟。而两个路由器之间的通信延迟时间则与这两个路由器通信路径上所有路由器中最大的交换延迟时间有关。 作为 M 公司网络部门的一名实习员工，现在要求你编写一个简单的程序来监视公司的网络状况。该程序能够随时更新网络状况的变化信息（路由器数据交换延迟时间的变化），并且根据询问给出两个路由器通信路径上延迟第 $k$ 大的路由器的延迟时间。 **** 【任务】 你的程序从输入文件中读入 $n$ 个路由器和 $n-1$ 条光缆的连接信息，每个路由器初始的数据交换延迟时间 $t_i$，以及 $q$ 条询问（或状态改变）的信息。并依次处理这 $q$ 条询问信息，它们可能是： 1. 由于更新了设备，或者设备出现新的故障，使得某个路由器的数据交换延迟时间发生了变化。 2. 查询某两个路由器 $a$ 和 $v$ 之间的路径上延迟第 $k$ 大的路由器的延迟时间。

无

无

【数据范围】 对于 $100\%$ 的数据，$1\le n,q \le 80000$，$0 \le k \le n$，任意一个路由器在任何时刻都满足延迟时间小于 $10^8$。