#6679. Unknow

内存限制:512 MiB 时间限制:1500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: -w-

题目描述

给定一棵 n 个节点的树,每个节点 i 有参数 k_i,b_i,l_i,r_i

Q 次询问:给出 u,v,x , 求 \max\{k_ix+b_i \ |\ i \in \mathrm{path}(u,v)\ \mathrm{and}\ x\in[l_i,r_i] \} (如果是空集则输出 0 )。

注:本题加强自「集训队互测2016」Unknown

输入格式

一行两个整数 n,Q

接下来 n 行每行四个整数 k_i,b_i,l_i,r_i

接下来 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 \le 10^5,\ 1\le u,v \le n,\ 0 \le k_i,l_i,r_i,x \le 10^6,\ 0 \le b_i \le 10^{12}, l_i \le r_i

子任务 数据范围 附加限制 分值
1 n,Q \le 100 / 13
2 n,Q \le 30000 24
3 n,Q \le 100000 保证树是一条链 35
4 / 28