题目描述
给定一棵 n 个节点的树,每个节点 i 有参数 ki,bi,li,ri。
共 Q 次询问:给出 u,v,x, 求 max{kix+bi ∣ i∈path(u,v) and x∈[li,ri]}(如果是空集则输出 0)。
注:本题加强自「集训队互测2016」Unknown
输入格式
一行两个整数 n,Q。
接下来 n 行每行四个整数 ki,bi,li,ri。
接下来 n−1 行每行两个整数 u,v。
接下来 Q 行每个三个整数 u,v,x。
输出格式
输出共 Q 行。
样例
5 5
1 3 1 5
2 0 2 5
1 5 3 5
1 2 4 5
3 5 5 5
1 2
1 3
2 4
2 5
4 5 1
3 5 2
4 2 3
5 3 4
5 4 5
0
5
6
9
20
数据范围与提示
n,Q≤105, 1≤u,v≤n, 0≤ki,li,ri,x≤106, 0≤bi≤1012,li≤ri
子任务 |
数据范围 |
附加限制 |
分值 |
1 |
n,Q≤100 |
/ |
13 |
2 |
n,Q≤30000 |
24 |
3 |
n,Q≤100000 |
保证树是一条链 |
35 |
4 |
/ |
28 |