Skip to content

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了,可以的话,请您参考添加页面,与大家一起分享你的题解!