1267: 这是什么数据结构？
题目
题目描述
数据结构往往和树有关，所以我们有一个 $n$ 个节点的树。
一棵树不够精彩，我们需要赋予每个节点不同的性质，所以每个节点就有了四个参数 $k_i, b_i, l_i, r_i$。
我们想要和这棵树进行交互，也就有了 $m$ 个询问：
给定 $u, v, x$，我们令 $P$ 表示 $u$ 到 $v$ 的简单路径上的节点，我们要求的就是 $\max(k_p x + b_p | p\in P ,x\in [l_p, r_p])$。
如果不存在这样的 $p$，那么输出一个 $0$。
输入格式
第一行两个整数 $n, m$ 代表了节点数量和询问数量。
接下来 $n$ 行，每行四个整数 $k_i, b_i, l_i, r_i$。
接下来 $n - 1$ 行，每行两个整数 $u, v$，代表树边。
接下来的 $m$ 行，每行三个整数 $u, v, x$，代表了一次询问。
输出格式
你需要输出 $m$ 行，代表了相应询问的答案。
样例输入
text
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
样例输出
text
0
5
6
9
20
数据范围
时间限制：1500 ms 空间限制：512 mb
全局限制
- $n, m \leq 10^5$
- $1\leq u, v \leq n$
- $0\leq k_i, l_i, r_i, x\leq 10^6, l_i\leq r_i$
- $0\leq b_i \leq 10^{12}$
部分限制
- $(\text{13 points})~n, m \leq 100$
- $(\text{24 points})~n, m \leq 30000$
- $(\text{35 points})$ 树是一条链
Oops! 本题目还没有解答！
助教老师们编题的速度，已经超过了解题的速度！
OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。
如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！