#1497. Unknow

Unknow

题目描述

给定一棵 nn 个节点的树,每个节点 ii 有参数 ki,bi,li,rik_i,b_i,l_i,r_i

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

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

输入格式

一行两个整数 n,Qn,Q

接下来 nn 行每行四个整数 ki,bi,li,rik_i,b_i,l_i,r_i

接下来 n1n-1 行每行两个整数 u,vu,v

接下来 QQ 行每个三个整数 u,v,xu,v,x

输出格式

输出共 QQ 行。

样例

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$

子任务 数据范围 附加限制 分值
11 n,Q100n,Q \le 100 / 1313
22 n,Q30000n,Q \le 30000 2424
33 n,Q100000n,Q \le 100000 保证树是一条链 3535
44 / 2828