P9175 [COCI 2022/2023 #4] Mreža

### 卡评测封号。

市长 Mirko 住在一个有 $n$ 个社区的城市里，这 $n$ 个社区用 $n-1$ 条双向道路连接，满足从任何社区出发都可以到达任意其他社区。 Mirko 想升级一些道路以疏导交通。对于每条路，我们知道目前在这条路上汽车的行驶速度 $v_i$，升级所需花费 $c_i$ 和升级后在这条路上汽车的行驶速度 $s_i$。 有 $q$ 个不满意的市民来见 Mirko。每个人都有他们自己的升级建议。第 $i$ 个市民的建议是：「我们应该在升级社区 $a_i$ 和 $b_i$ 之间的道路上投资 $e_i$ 欧元。」 对于每个建议，Mirko 感兴趣的是，如果他的目标是使社区 $a_i$ 和 $b_i$ 之间的最低驾驶速度最大化，那么他在升级道路上最多花费 $e_i$ 欧元的话这个最低驾驶速度是多少。 Mirko 瞬间意识到这个问题不简单，并且他雇佣你来帮助他！

第一行包含一个整数 $n\ (2\le n\le 10^5)$，表示社区总数。 接下来 $n-1$ 行，每行五个整数 $x_i,y_i,v_i,c_i,s_i\ (1\le x_i,y_i\le n,1\le v_i

输出 $q$ 行，表示对每个市民建议的答案。

样例解释 $1$：下图展示了这个城市和社区。边上写的分别是目前汽车的行驶速度，升级花费和升级后的汽车行驶速度。  如果我们升级 $1$ 和 $2$，$1$ 和 $3$ 之间的道路，从 $2$ 到 $4$ 的行驶速度将变成 $10,9,7$。最小为 $7$。 如果我们升级 $4$ 和 $3$ 之间的道路，从 $6$ 到 $4$ 的行驶速度将变成 $5,15$。最小为 $5$。 如果我们升级 $3$ 和 $5$ 之间的道路，从 $5$ 到 $3$ 的行驶速度将变成 $11$。 |子任务编号| 附加限制| 分值| |:-:|:-:|:-:| | $0$ | 是样例 | $0$ | | $1$ | $n,q\le 1000$ | $19$ | | $2$ | 每个社区最多与两个其他社区相连 | $26$ | | $3$ | 无附加限制 | $55$ |