[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 进行操作,输出一行一个数,表示他能够选择的最小的数字

输入输出样例

输入样例 #1

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

输出样例 #1

123456789123456789
6
-106

说明

测试点 1 ~ 2:$ n \leq 10 $,$ m \leq 10 $,$ | a | \leq 10000 $; 测试点 3 ~ 4:$ n \leq 1000 $,$ m \leq 1000 $,$ | a | \leq 10000 $; 测试点 5:$ n \leq 100000 $,$ m \leq 100000 $,$ a = 0 $,树是一条链; 测试点 6 ~ 7:$ n \leq 100000 $,$ m \leq 100000 $,$ a = 0 $; 测试点 8:$ n \leq 100000 $,$ m \leq 100000 $,$ a = 1 $,树是一条链; 测试点 9 ~ 10:$ n \leq 100000 $,$ m \leq 100000 $,$ a = 1 $; 测试点 11 ~ 13:$ n \leq 100000 $,$ m \leq 100000 $,$ | a | \leq 10000 $,树是一条链; 测试点 14 ~ 20:$ n \leq 100000 $,$ m \leq 100000 $,$ | a | \leq 10000 $。 对于所有数据,$0\le w, |b|\le 10^9$。