P4069 [SDOI2016] 游戏

Alice 和 Bob 在玩一个游戏。 游戏在一棵有 $n$ 个点的树上进行。最初，每个点上都只有一个数字，那个数字是 $123456789123456789$。 有时，Alice 会选择一条从 $s$ 到 $t$ 的路径，在这条路径上的每一个点上都添加一个数字。对于路径上的一个点 $r$，若 $r$ 与 $s$ 的距离是 $dis$，那么 Alice 在点 $r$ 上添加的数字是 $a\times dis+b$。 有时，Bob 会选择一条从 $s$ 到 $t$ 的路径。他需要先从这条路径上选择一个点，再从那个点上选择一个数字。 Bob 选择的数字越小越好，但大量的数字让 Bob 眼花缭乱。Bob 需要你帮他找出他能够选择的最小的数字。

第一行两个数字 $n,m$，表示树的点数和进行的操作数。 接下来 $n-1$ 行，每行三个数字 $u,v,w$，表示树上有一条连接 $u,v$ 的边，长度是 $w$。 接下来 $m$ 行。每行第一个数字是 $1$ 或 $2$。 若第一个数是 $1$，表示 Alice 进行操作，接下来四个数字 $s,t,a,b$。 若第一个数是 $2$，表示 Bob 进行操作，接下来两个数字 $s,t$。

每当 Bob 进行操作，输出一行一个数，表示他能够选择的最小的数字

::cute-table{tuack} |测试点编号|$n,m\le$|$\lvert a\rvert\le$|特殊性质| |:-:|:-:|:-:|:-:| |$1\sim 2$|$10$|$10^4$|无| |$3\sim 4$|$10^3$|$10^4$|^| |$5$|$10^5$|$0$|树是一条链| |$6\sim 7$|^|^|无| |$8$|^|$=1$|树是一条链| |$9\sim 10$|^|^|无| |$11\sim 13$|^|$10^4$|树是一条链| |$14\sim 20$|^|^|无| 对于所有数据，$0\le w, \lvert b\rvert\le 10^9$。