CF593D Happy Tree Party
题目描述
为了庆祝博格丹的生日，他的母亲送给他一棵有$n$个节点的树，树的第$i$条边上写了一个数字$x_i$。顺带提醒一下，一棵树指的是一个由无向边连接的无环连通图。在礼物被送出之后，有$m$位访客陆续来到博格丹家中参加派对。第$i$位访客会进行如下两种操作其中之一：
>1.选择一个数$y_i$和两个节点$a_i$、$b_i$。在这之后，他会沿着树的边走一遍从$a_i$到$b_i$的最短路（当然，在树上这样的路径只有一条）。每当他经过一条边$j$时，他选择的数$y_i$会立刻变成$\lfloor \frac{y_i}{x_j} \rfloor$，也就是$\frac{y_i}{x_i}$向下取整。
>
>2.选择第$j$条边$p_j$，把它的边权$x_{p_i}$改成一个正整数$c_i \in [1,x_{p_i}]$。
由于博格丹很替他的客人们着想，他决定简化这个过程。你需要写一个程序处理访客们的操作，并且对于每一个第一种操作$i$，输出$y_i$最后的值。
输入格式
输入的第一行包含两个整数$n$、$m$（$2\le n\le200000$，$1\le m\le200000$），分别表示树的节点数和访客的数量。
接下来$n-1$行描述每一条边的信息。这些行中的第$i$行包含三个整数$u_i$，$v_i$，$x_i$（$1\le u_i,v_i\le n,u_i\ne v_i,1\le x_i \le 10^{18}$），表示节点$u_i$和$v_i$之间有一条写有$x_i$的无向边。
接下来$m$行描述访客们的操作。每一行包含三个或者四个整数，有如下两种情况：
* $1\ a_i\ b_i\ y_i\ $表示操作1
* $2\ p_i\ c_i\ $表示操作2
你可以认为每一个询问都是合法的，也就是说$1\le a_i,b_i\le n$，$1\le p_i\le n-1$，$1\le y_i\le10^{18}$并且$1\le c_i\le x_{p_i}$，此时的$x_{p_i}$不一定和最开始的$x_{p_i}$相等，因为它可能已经被更新过。所有边按照$1\sim n-1$的标号依次在输入中给出。
输出格式
对于每一个询问1，输出一行，从$a_i$走到$b_i$后$y_i$最终的值
说明/提示
Initially the tree looks like this:
The response to the first query is:  = 2
After the third edge is changed, the tree looks like this:
The response to the second query is:  = 4
In the third query the initial and final vertex coincide, that is, the answer will be the initial number 20.
After the change in the fourth edge the tree looks like this:
In the last query the answer will be:  = 3