#2032. 「SDOI2016」游戏

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 11Dimensions

题目描述

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: n \leq 10 m \leq 10 \left| a \right| \leq 10000
测试点 3 ~ 4: n \leq 1000 m \leq 1000 \left| a \right| \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 \left| a \right| \leq 10000 ,树是一条链;
测试点 14 ~ 20: n \leq 100000 m \leq 100000 \left| a \right| \leq 10000