4501. Unknow

【题目描述】

给定一颗 $n$ 个点的树，每个节点 $i$ 有参数 $k_i,b_i,l_i,r_i$。

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

【输入格式】

一行两个整数 $n,Q$。

接下来 $n$ 行，每行两个整数 $k_i,b_i,l_i,r_i$。

接下来 $n-1$ 行，每行两个整数 $u_i,v_i$，表示树上的一条边。

接下来 $Q$ 行，每行三个整数，$u_i,v_i,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

【数据规模与约定】

对于 6% 的数据，$n,Q\le 100$。

对于另外 18% 的数据，$n,Q\le 30000$。

对于另外 24% 的数据，保证树是一条链。

对于 100% 的数据，$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$。