#P4069. [SDOI2016] 游戏

    ID: 5007 远端评测题 1000ms 250MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2016线段树各省省选山东最近公共祖先,LCA树链剖分,树剖

[SDOI2016] 游戏

题目描述

Alice 和 Bob 在玩一个游戏。

游戏在一棵有 nn 个点的树上进行。最初,每个点上都只有一个数字,那个数字是 123456789123456789123456789123456789

有时,Alice 会选择一条从 sstt 的路径,在这条路径上的每一个点上都添加一个数字。对于路径上的一个点 rr,若 rrss 的距离是 disdis,那么 Alice 在点 rr 上添加的数字是 a×dis+ba\times dis+b

有时,Bob 会选择一条从 sstt 的路径。他需要先从这条路径上选择一个点,再从那个点上选择一个数字。

Bob 选择的数字越小越好,但大量的数字让 Bob 眼花缭乱。Bob 需要你帮他找出他能够选择的最小的数字。

输入格式

第一行两个数字 n,mn,m,表示树的点数和进行的操作数。

接下来 n1n-1 行,每行三个数字 u,v,wu,v,w,表示树上有一条连接 u,vu,v 的边,长度是 ww

接下来 mm 行。每行第一个数字是 1122

若第一个数是 11,表示 Alice 进行操作,接下来四个数字 s,t,a,bs,t,a,b

若第一个数是 22,表示 Bob 进行操作,接下来四个数字 s,ts,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:n10 n \leq 10 m10 m \leq 10 a10000 | a | \leq 10000

测试点 3 ~ 4:n1000 n \leq 1000 m1000 m \leq 1000 a10000 | a | \leq 10000

测试点 5:n100000 n \leq 100000 m100000 m \leq 100000 a=0 a = 0 ,树是一条链;

测试点 6 ~ 7:n100000 n \leq 100000 m100000 m \leq 100000 a=0 a = 0

测试点 8:n100000 n \leq 100000 m100000 m \leq 100000 a=1 a = 1 ,树是一条链;

测试点 9 ~ 10:n100000 n \leq 100000 m100000 m \leq 100000 a=1 a = 1

测试点 11 ~ 13:n100000 n \leq 100000 m100000 m \leq 100000 a10000 | a | \leq 10000 ,树是一条链;

测试点 14 ~ 20:n100000 n \leq 100000 m100000 m \leq 100000 a10000 | a | \leq 10000

对于所有数据,0w,b1090\le w, |b|\le 10^9