查询从 U 到 V 所需的最低燃料
Queries for minimum fuel needed to travel from U to V
问题：
给定一棵有 N 个节点的树。
树的每条边包含：
D : 边的长度T：通过那条边需要支付的金币（金币应该在通过边之前支付）
通过边缘移动时，如果您携带 X 金币，则需要 X*D 燃料。
有两种类型的查询：
- u, v: 找到将
G 金币从 u 转移到 v 所需的燃料（G 在所有查询中都是固定的）
- u, v, x: 将边
{u,v}的T更新为x（{u, v}保证在树中）
约束条件：
2 ≤ N ≤ 100.000
1 ≤ Q ≤ 100.000
1 ≤ Ai, Bi ≤ N
1 ≤ D, T, G ≤ 10^9
示例：
N = 6, G = 2
以 u = 3 和 v = 6 的查询 1 为例。首先，您从 3 开始，使用 11 golds ，支付 2，有 9，然后使用 9*1 = 9 燃料前往节点 2。接下来，我们支付 3 金币，有 6 金币，并使用 6*2 = 12 燃料前往节点 4。最后，我们支付 4，有 2 个金币，并使用 2*1 = 2 燃料前往节点 6。所以需要的燃料是 9 + 12 + 2 = 23.
所以查询的答案：u = 3, v = 6 将是 23
第二个查询只是更新边的T，所以我认为不需要解释。
我的看法
我只解决了 O(N*Q) 的问题。因为它是一棵树，所以从 u 到 v 只有一条路径，所以对于每个查询，我都会执行 DFS 来查找从 u 到 v 所需的燃料。这是该子任务的代码：https://ideone.com/SyINTQ
对于一些特殊情况，所有T都为0，我们只需要找到u到v的长度，然后乘以G。[=32的长度=] 到 v 可以使用距离数组和 LCA 轻松找到。我认为这可能是正确解决方案的提示。
有没有办法以 logN 或更少的形式进行查询？
P/S:如果有什么需要澄清的请评论，对不起我的英语不好。
我在评论中说过Dijkstra算法是必要的，但更好地思考DFS确实足够了，因为每对顶点只有一条路径，我们总是需要从起点到终点.
使用优先级队列而不是堆栈只会改变图的探索顺序，但在最坏的情况下它仍会访问所有顶点。
使用队列而不是堆栈会使算法成为广度优先搜索，同样只会改变探索图的顺序。
假设给定距离内的节点数随阈值呈指数增长。可以通过进行两次搜索并在中间相遇来实现对典型案例的改进。但只是一个常数。
所以我认为最好采用简单的解决方案，在 C/C++ 中实现它会使程序快几十倍。
解决方案
准备邻接表，同时使图无向
from collections import defaultdict
def process_edges(rows):
edges = defaultdict(list)
for u,v,D,T in rows:
edges[u].append((v,(D,T)))
edges[v].append((u,(D,T)))
return edges
向后搜索很有趣，因为黄金的数量在目的地是固定的，而在起点是未知的，那么我们可以计算出每个节点向后搜索所需的黄金和燃料的确切数量。
当然你可以去掉我留在那里的打印语句
def dfs(edges, a, b, G):
Q = [((0,G),b)]
visited = set()
while len(Q) != 0:
((Fu,Gu), current_vertex) = Q.pop()
visited.add(current_vertex)
for neighbor,(D,T) in edges[current_vertex]:
if neighbor in visited:
continue; # avoid going backwards
Gv = Gu + T # add the tax of the edge to the gold budget
Fv = Fu + Gv * D # compute the required fuel
print(neighbor, (Fv, Gv))
if neighbor == a:
return (Fv, Gv)
Q.append(((Fv,Gv), neighbor))
运行 你的例子
edges = process_edges([
[6,4,1,4],
[5,4,2,2],
[4,2,2,3],
[3,2,1,2],
[1,2,2,1]
])
dfs(edges,3,6,2)
将打印：
4 (6, 6)
5 (22, 8)
2 (24, 9)
3 (35, 11)
和return(35, 11)。也就是说从3到6的rounte需要11金币，35是消耗的燃料。
这个回答会详细解释我的矩阵群评论然后
勾勒出使其工作所需的标准数据结构。
假设我们携带 Gold 并且到目前为止已经燃烧了 Fuel。
如果我们遍历一条带参数Distance、Toll的边，那么
效果是
Gold -= Toll
Fuel += Gold * Distance,
或作为功能程序，
Gold' = Gold - Toll
Fuel' = Fuel + Gold' * Distance.
= Fuel + Gold * Distance - Toll * Distance.
后面的代码片段定义了数学家所说的动作：
每个 Distance, Toll 产生一个从 Gold, Fuel 到
Gold, Fuel.
现在，每当我们有两个函数从一个域到同一个域时，
我们可以组合它们（一个接一个地应用）：
Gold' = Gold - Toll1
Fuel' = Fuel + Gold' * Distance1,
Gold'' = Gold' - Toll2
Fuel'' = Fuel' + Gold'' * Distance2.
这个数学的重点是我们可以扩展定义：
Gold'' = Gold - Toll1 - Toll2
= Gold - (Toll1 + Toll2),
Fuel'' = Fuel' + (Gold - (Toll1 + Toll2)) * Distance2
= Fuel + (Gold - Toll1) * Distance1 + (Gold - (Toll1 + Toll2)) * Distance2
= Fuel + Gold * (Distance1 + Distance2) - (Toll1 * Distance1 + (Toll1 + Toll2 ) * Distance2).
我试着用和以前一样的形式来表达Fuel''：
composition 有“Distance”Distance1 + Distance2 和“Toll”
Toll1 + Toll2，但最后一项不符合模式。我们能做什么
但是，要做的是添加另一个参数 FuelSaved 并将其定义为
Toll * Distance 对于每个输入边。广义更新
规则是
Gold' = Gold - Toll
Fuel' = Fuel + Gold * Distance - FuelSaved.
我会让你计算出广义的构图规则
Distance1, Toll1, FuelSaved1 和 Distance2, Toll2, FuelSaved2。
可以这么说，我们可以将 Gold, Fuel 作为列向量嵌入
{1, Gold, Fuel}和参数Distance, Toll, FuelSaved为一个单元
下三角矩阵
{{1, 0, 0}, {-Toll, 1, 0}, {-FuelSaved, Distance, 1}}。然后
组合是矩阵乘法。
现在，到目前为止我们只有一个半群。我可以从这里拿走它
数据结构，但是当我们没有
减法的模拟（对于直觉，比较发现的问题
数组中每个长度 k window 的总和，并找到最大值）。
令人高兴的是，这里有一个有用的概念来撤销遍历（逆）。
我们可以通过从 Gold'、Fuel':
求解 Gold、Fuel 来推导出它
Gold = Gold' + Toll
Fuel = Fuel' - Gold * Distance + FuelSaved,
Fuel = Fuel' + Gold' * (-Distance) - (-FuelSaved - Toll * Distance)
并读取逆参数。
我答应了数据结构的草图，所以我们到了。扎根
任何地方的树。能够
就够了
- 给定节点u和v，查询u和v的最叶共同祖先；
- 给定一个节点u，查询从u到根的参数；
- 给定一个节点v，查询从根到v的参数；
- 更新边上的通行费。
然后为了回答查询 u, v，我们查询它们的最叶共同祖先 w
和 return 组合的燃料成本（u 到根）（w 到根）⁻¹
（根到 w）⁻¹（根到 v）其中 ⁻¹ 表示“取反”。
这里全面的大锤方法是实现动态树，
这将完成 所有这些
things 以摊销对数形式
每次操作的时间。但是我们不需要动态拓扑更新并且可以
可能负担得起一个额外的对数因子，所以一组更容易消化
件将是最叶共同祖先，重路径分解，和
分段树（每条路径一个；Fenwick 可能是另一种选择，但是
我不确定非交换运算可能会带来什么并发症
创建）。
问题：
给定一棵有 N 个节点的树。
树的每条边包含：
D: 边的长度T：通过那条边需要支付的金币（金币应该在通过边之前支付）
通过边缘移动时，如果您携带 X 金币，则需要 X*D 燃料。
有两种类型的查询：
- u, v: 找到将
G金币从 u 转移到 v 所需的燃料（G在所有查询中都是固定的） - u, v, x: 将边
{u,v}的T更新为x（{u, v}保证在树中）
约束条件：
2 ≤ N ≤ 100.000
1 ≤ Q ≤ 100.000
1 ≤ Ai, Bi ≤ N
1 ≤ D, T, G ≤ 10^9
示例：
N = 6, G = 2
以 u = 3 和 v = 6 的查询 1 为例。首先，您从 3 开始，使用 11 golds ，支付 2，有 9，然后使用 9*1 = 9 燃料前往节点 2。接下来，我们支付 3 金币，有 6 金币，并使用 6*2 = 12 燃料前往节点 4。最后，我们支付 4，有 2 个金币，并使用 2*1 = 2 燃料前往节点 6。所以需要的燃料是 9 + 12 + 2 = 23.
所以查询的答案：u = 3, v = 6 将是 23
第二个查询只是更新边的T，所以我认为不需要解释。
我的看法
我只解决了 O(N*Q) 的问题。因为它是一棵树，所以从 u 到 v 只有一条路径，所以对于每个查询，我都会执行 DFS 来查找从 u 到 v 所需的燃料。这是该子任务的代码：https://ideone.com/SyINTQ
对于一些特殊情况，所有T都为0，我们只需要找到u到v的长度，然后乘以G。[=32的长度=] 到 v 可以使用距离数组和 LCA 轻松找到。我认为这可能是正确解决方案的提示。
有没有办法以 logN 或更少的形式进行查询？
P/S:如果有什么需要澄清的请评论，对不起我的英语不好。
我在评论中说过Dijkstra算法是必要的，但更好地思考DFS确实足够了，因为每对顶点只有一条路径，我们总是需要从起点到终点.
使用优先级队列而不是堆栈只会改变图的探索顺序，但在最坏的情况下它仍会访问所有顶点。
使用队列而不是堆栈会使算法成为广度优先搜索，同样只会改变探索图的顺序。
假设给定距离内的节点数随阈值呈指数增长。可以通过进行两次搜索并在中间相遇来实现对典型案例的改进。但只是一个常数。
所以我认为最好采用简单的解决方案，在 C/C++ 中实现它会使程序快几十倍。
解决方案
准备邻接表，同时使图无向
from collections import defaultdict
def process_edges(rows):
edges = defaultdict(list)
for u,v,D,T in rows:
edges[u].append((v,(D,T)))
edges[v].append((u,(D,T)))
return edges
向后搜索很有趣，因为黄金的数量在目的地是固定的，而在起点是未知的，那么我们可以计算出每个节点向后搜索所需的黄金和燃料的确切数量。
当然你可以去掉我留在那里的打印语句
def dfs(edges, a, b, G):
Q = [((0,G),b)]
visited = set()
while len(Q) != 0:
((Fu,Gu), current_vertex) = Q.pop()
visited.add(current_vertex)
for neighbor,(D,T) in edges[current_vertex]:
if neighbor in visited:
continue; # avoid going backwards
Gv = Gu + T # add the tax of the edge to the gold budget
Fv = Fu + Gv * D # compute the required fuel
print(neighbor, (Fv, Gv))
if neighbor == a:
return (Fv, Gv)
Q.append(((Fv,Gv), neighbor))
运行 你的例子
edges = process_edges([
[6,4,1,4],
[5,4,2,2],
[4,2,2,3],
[3,2,1,2],
[1,2,2,1]
])
dfs(edges,3,6,2)
将打印：
4 (6, 6)
5 (22, 8)
2 (24, 9)
3 (35, 11)
和return(35, 11)。也就是说从3到6的rounte需要11金币，35是消耗的燃料。
这个回答会详细解释我的矩阵群评论然后 勾勒出使其工作所需的标准数据结构。
假设我们携带 Gold 并且到目前为止已经燃烧了 Fuel。
如果我们遍历一条带参数Distance、Toll的边，那么
效果是
Gold -= Toll
Fuel += Gold * Distance,
或作为功能程序，
Gold' = Gold - Toll
Fuel' = Fuel + Gold' * Distance.
= Fuel + Gold * Distance - Toll * Distance.
后面的代码片段定义了数学家所说的动作：
每个 Distance, Toll 产生一个从 Gold, Fuel 到
Gold, Fuel.
现在，每当我们有两个函数从一个域到同一个域时， 我们可以组合它们（一个接一个地应用）：
Gold' = Gold - Toll1
Fuel' = Fuel + Gold' * Distance1,
Gold'' = Gold' - Toll2
Fuel'' = Fuel' + Gold'' * Distance2.
这个数学的重点是我们可以扩展定义：
Gold'' = Gold - Toll1 - Toll2
= Gold - (Toll1 + Toll2),
Fuel'' = Fuel' + (Gold - (Toll1 + Toll2)) * Distance2
= Fuel + (Gold - Toll1) * Distance1 + (Gold - (Toll1 + Toll2)) * Distance2
= Fuel + Gold * (Distance1 + Distance2) - (Toll1 * Distance1 + (Toll1 + Toll2 ) * Distance2).
我试着用和以前一样的形式来表达Fuel''：
composition 有“Distance”Distance1 + Distance2 和“Toll”
Toll1 + Toll2，但最后一项不符合模式。我们能做什么
但是，要做的是添加另一个参数 FuelSaved 并将其定义为
Toll * Distance 对于每个输入边。广义更新
规则是
Gold' = Gold - Toll
Fuel' = Fuel + Gold * Distance - FuelSaved.
我会让你计算出广义的构图规则
Distance1, Toll1, FuelSaved1 和 Distance2, Toll2, FuelSaved2。
可以这么说，我们可以将 Gold, Fuel 作为列向量嵌入
{1, Gold, Fuel}和参数Distance, Toll, FuelSaved为一个单元
下三角矩阵
{{1, 0, 0}, {-Toll, 1, 0}, {-FuelSaved, Distance, 1}}。然后
组合是矩阵乘法。
现在，到目前为止我们只有一个半群。我可以从这里拿走它
数据结构，但是当我们没有
减法的模拟（对于直觉，比较发现的问题
数组中每个长度 k window 的总和，并找到最大值）。
令人高兴的是，这里有一个有用的概念来撤销遍历（逆）。
我们可以通过从 Gold'、Fuel':
Gold、Fuel 来推导出它
Gold = Gold' + Toll
Fuel = Fuel' - Gold * Distance + FuelSaved,
Fuel = Fuel' + Gold' * (-Distance) - (-FuelSaved - Toll * Distance)
并读取逆参数。
我答应了数据结构的草图，所以我们到了。扎根 任何地方的树。能够
就够了- 给定节点u和v，查询u和v的最叶共同祖先；
- 给定一个节点u，查询从u到根的参数；
- 给定一个节点v，查询从根到v的参数；
- 更新边上的通行费。
然后为了回答查询 u, v，我们查询它们的最叶共同祖先 w 和 return 组合的燃料成本（u 到根）（w 到根）⁻¹ （根到 w）⁻¹（根到 v）其中 ⁻¹ 表示“取反”。
这里全面的大锤方法是实现动态树， 这将完成 所有这些 things 以摊销对数形式 每次操作的时间。但是我们不需要动态拓扑更新并且可以 可能负担得起一个额外的对数因子，所以一组更容易消化 件将是最叶共同祖先，重路径分解，和 分段树（每条路径一个；Fenwick 可能是另一种选择，但是 我不确定非交换运算可能会带来什么并发症 创建）。