4061: 「SDOI2016」游戏
内存限制：256 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
Alice 和 Bob 在玩一个游戏。
游戏在一棵有 $n$ 个点的树上进行。最初，每个点上都只有一个数字，那个数字是 $123456789123456789$。
有时，Alice 会选择一条从 $s$ 到 $t$ 的路径，在这条路径上的每一个点上都添加一个数字。对于路径上的一个点 $r$，若 $r$ 与 $s$ 的距离是 $\mathrm{dis}$，那么 Alice 在点 $r$ 上添加的数字是 $a\cdot \mathrm{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 进行操作，输出一行一个数，表示他能够选择的最小的数字。
样例输入 复制
3 5
1 2 10
2 3 20
2 1 3
1 2 3 5 6
2 2 3
1 2 3 -5 -6
2 2 3样例输出 复制
123456789123456789
6
-106提示
数据范围：测试点 1 ~ 2：$1\le n \leq 10 $，$1\le m \leq 10 $，$ \left| a \right| \leq 10000 $； 测试点 3 ~ 4：$1\le n \leq 1000 $，$1\le m \leq 1000 $，$ \left| a \right| \leq 10000 $； 测试点 5：$1\le n \leq 100000 $，$1\le m \leq 100000 $，$ a = 0 $，树是一条链； 测试点 6 ~ 7：$1\le n \leq 100000 $，$1\le m \leq 100000 $，$ a = 0 $； 测试点 8：$1\le n \leq 100000 $，$1\le m \leq 100000 $，$ a = 1 $，树是一条链； 测试点 9 ~ 10：$1\le n \leq 100000 $，$1\le m \leq 100000 $，$ a = 1 $； 测试点 11 ~ 13：$1\le n \leq 100000 $，$1\le m \leq 100000 $，$ \left| a \right| \leq 10000 $，树是一条链； 测试点 14 ~ 20：$1\le n \leq 100000 $，$1\le m \leq 100000 $，$ \left| a \right| \leq 10000 $，$1\le u,v,s,t\le n$，$1\le w\le 10^9$，$|b|\le 10^9$。