{"problem":{"name":"[COCI 2022/2023 #4] Mreža","description":{"content":"市长 Mirko 住在一个有 $n$ 个社区的城市里，这 $n$ 个社区用 $n-1$ 条双向道路连接，满足从任何社区出发都可以到达任意其他社区。 Mirko 想升级一些道路以疏导交通。对于每条路，我们知道目前在这条路上汽车的行驶速度 $v_i$，升级所需花费 $c_i$ 和升级后在这条路上汽车的行驶速度 $s_i$。 有 $q$ 个不满意的市民来见 Mirko。每个人都有他们自己的升级建议。","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":5000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9175"},"statements":[{"statement_type":"Markdown","content":"市长 Mirko 住在一个有 $n$ 个社区的城市里，这 $n$ 个社区用 $n-1$ 条双向道路连接，满足从任何社区出发都可以到达任意其他社区。\n\nMirko 想升级一些道路以疏导交通。对于每条路，我们知道目前在这条路上汽车的行驶速度 $v_i$，升级所需花费 $c_i$ 和升级后在这条路上汽车的行驶速度 $s_i$。\n\n有 $q$ 个不满意的市民来见 Mirko。每个人都有他们自己的升级建议。第 $i$ 个市民的建议是：「我们应该在升级社区 $a_i$ 和 $b_i$ 之间的道路上投资 $e_i$ 欧元。」\n\n对于每个建议，Mirko 感兴趣的是，如果他的目标是使社区 $a_i$ 和 $b_i$ 之间的最低驾驶速度最大化，那么他在升级道路上最多花费 $e_i$ 欧元的话这个最低驾驶速度是多少。\n\nMirko 瞬间意识到这个问题不简单，并且他雇佣你来帮助他！\n\n## Input\n\n第一行包含一个整数 $n\\ (2\\le n\\le 10^5)$，表示社区总数。\n\n接下来 $n-1$ 行，每行五个整数 $x_i,y_i,v_i,c_i,s_i\\ (1\\le x_i,y_i\\le n,1\\le v_i<s_i\\le 10^9,1\\le c_i\\le 10^9)$，表示社区 $x_i$ 和 $y_i$ 之间有一条路相连，目前在这条路上汽车的行驶速度为 $v_i$，升级所需花费为 $c_i$，升级后在这条路上汽车的行驶速度为 $s_i$。\n\n接下来一行一个整数 $q\\ (1\\le q\\le 10^5)$，表示不满意的市民总数。\n\n接下来 $q$ 行，每行三个整数 $a_i,b_i,e_i\\ (1\\le a_i,b_i\\le n,a_i\\neq b_i,1\\le e_i\\le 10^{18})$，意义如题目描述。\n\n## Output\n\n输出 $q$ 行，表示对每个市民建议的答案。\n\n[samples]\n\n## Background\n\n### 卡评测封号。\n\n## Note\n\n样例解释 $1$：下图展示了这个城市和社区。边上写的分别是目前汽车的行驶速度，升级花费和升级后的汽车行驶速度。\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/umum0365.png?x-oss-process=image/resize,m_lfit,h_1700,w_2250)\n\n如果我们升级 $1$ 和 $2$，$1$ 和 $3$ 之间的道路，从 $2$ 到 $4$ 的行驶速度将变成 $10,9,7$。最小为 $7$。\n\n如果我们升级 $4$ 和 $3$ 之间的道路，从 $6$ 到 $4$ 的行驶速度将变成 $5,15$。最小为 $5$。\n\n如果我们升级 $3$ 和 $5$ 之间的道路，从 $5$ 到 $3$ 的行驶速度将变成 $11$。\n\n|子任务编号|\t附加限制|\t分值|\n|:-:|:-:|:-:|\n| $0$ | 是样例 | $0$ |\n| $1$ | $n,q\\le 1000$ |\t$19$ |\n| $2$ |\t每个社区最多与两个其他社区相连 | $26$ |\n| $3$ |\t无附加限制 | $55$ |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9175","tags":["2022","可持久化线段树","整体二分","COCI（克罗地亚）"],"sample_group":[["6\n1 2 5 7 10\n1 3 4 8 9\n3 4 7 1 15\n3 5 6 3 11\n3 6 5 6 8\n3\n2 4 15\n6 4 5\n3 5 10","7\n5\n11"],["4\n1 2 5 5 8\n2 3 4 6 9\n3 4 6 10 7\n4\n1 4 16\n2 4 16\n1 4 10\n3 4 10","6\n7\n5\n7"]],"created_at":"2026-03-03 11:09:25"}}