Queries for minimum fuel needed to travel from U to V

Question

Question:

Given a tree with N nodes.

Each edges of the tree contains:

• D : the length of the edge
• T : the gold needed to pay to go through that edge (the gold should be paid before going through the edge)

When moving through an edge, if you're carrying X golds, you will need X*D fuel.

There are 2 types of queries:

• u, v: find the fuel needed to transfer G golds from u to v (G is fixed among all queries)
• u, v, x: update T of edge {u,v} to x ({u, v} is guaranteed to be in the tree)

Constraints:

2 ≤ N ≤ 100.000
1 ≤ Q ≤ 100.000
1 ≤ Ai, Bi ≤ N
1 ≤ D, T, G ≤ 10^9

Example:

N = 6, G = 2

Take queries 1 with u = 3 and v = 6 for example. First, you start at 3 with 11 golds , pay 2, having 9, and go to node 2 with 9*1 = 9 fuel. Next, we pay 3 gold, having 6, and go to node 4 with 6*2 = 12 fuel. Finally, we pay 4, having 2 gold, and go to node 6 with 2*1 = 2 fuel. So the fuel needed would be 9 + 12 + 2 = 23.

So the answer to query: u = 3, v = 6 would be 23

The second query is just updating T of the edge so I think there's no need for explanation.

My take

I was only able to solve the problem in O(N*Q). Since it's a tree, there's only 1 path from u to v, so for each query, I do a DFS to find the fuel needed to go from u to v. Here's the code for that subtask: https://ideone.com/SyINTQ

For some special cases that all T are 0. We just need to find the length from u to v and multiply it by G. The length from u to v can be easily found using a distance array and LCA. I think this could be a hint for the proper solution.

Is there a way to do the queries in logN or less?

P/S: Please comment if anything needs to be clarified, and sorry for my bad English.

Answer 1

This answer will explain my matrix group comment in detail and then sketch the standard data structures needed to make it work.

Let’s suppose that we’re carrying Gold and have burned Fuel so far. If we traverse an edge with parameters Distance, Toll, then the effect is

Gold -= Toll
Fuel += Gold * Distance,

or as a functional program,

Gold' = Gold - Toll
Fuel' = Fuel + Gold' * Distance.
= Fuel + Gold * Distance - Toll * Distance.

The latter code fragment defines what mathematicians call an action: each Distance, Toll gives rise to a function from Gold, Fuel to Gold, Fuel.

Now, whenever we have two functions from a domain to that same domain, we can compose them (apply one after the other):

Gold' = Gold - Toll1
Fuel' = Fuel + Gold' * Distance1,

Gold'' = Gold' - Toll2
Fuel'' = Fuel' + Gold'' * Distance2.

The point of this math is that we can expand the definitions:

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).

I’ve tried to express Fuel'' in the same form as before: the composition has “Distance” Distance1 + Distance2 and “Toll” Toll1 + Toll2, but the last term doesn’t fit the pattern. What we can do, however, is add another parameter, FuelSaved and define it to be Toll * Distance for each of the input edges. The generalized update rule is

Gold' = Gold - Toll
Fuel' = Fuel + Gold * Distance - FuelSaved.

I’ll let you work out the generalized composition rule for Distance1, Toll1, FuelSaved1 and Distance2, Toll2, FuelSaved2. Suffice it to say, we can embed Gold, Fuel as a column vector {1, Gold, Fuel}, and parameters Distance, Toll, FuelSaved as a unit lower triangular matrix {{1, 0, 0}, {-Toll, 1, 0}, {-FuelSaved, Distance, 1}}. Then composition is matrix multiplication.

Now, so far we only have a semigroup. I could take it from here with data structures, but they’re more complicated when we don’t have an analog of subtraction (for intuition, compare the problems of finding the sum of each length-k window in an array with finding the max). Happily, there is a useful notion of undoing a traversal here (inverse). We can derive it by solving for Gold, Fuel from Gold', Fuel':

Gold = Gold' + Toll
Fuel = Fuel' - Gold * Distance + FuelSaved,
Fuel = Fuel' + Gold' * (-Distance) - (-FuelSaved - Toll * Distance)

and reading off the inverse parameters.

I promised a sketch of the data structures, so here we are. Root the tree anywhere. It suffices to be able to

• Given nodes u and v, query the leafmost common ancestor of u and v;
• Given a node u, query the parameters to get from u to the root;
• Given a node v, query the parameters to get from the root to v;
• Update the toll on an edge.

Then to answer a query u, v, we query their leafmost common ancestor w and return the fuel cost of the composition (u to root) (w to root)⁻¹ (root to w)⁻¹ (root to v) where ⁻¹ means “take the inverse”.

The full-on sledgehammer approach here is to implement dynamic trees, which will do all of these things in amortized logarithmic time per operation. But we don’t need dynamic topology updates and can probably afford an extra log factor, so a set of more easily digestable pieces would be leafmost common ancestors, heavy path decomposition, and segment trees (one per path; Fenwick is potentially another option, but I’m not sure what complications a noncommutative operation might create).

Answer 2

I told in the comments that a Dijkstra algorithm was necessary, but thinking better the DFS is really enough because there is only one path for each pair of vertices, we will always need to go from the starting point to the endpoint.

Using a priority queue instead of a stack would only change the order that the graph is explored, but in the worst case it would still visit all the vertices.

Using a queue instead of a stack would make the algorithm a breadth first search, again would only change the order in which the graph is explored.

Assuming that the number of nodes in a given distance increases exponentially with the threshold. An improvement for the typical case could be achieved by doing two searches and meeting in the middle. But only a constant factor.

So I think it is better to go with the simple solution, implementing this in C/C++ will result in a program dozens of times faster.

Solution

Prepare adjacency lists, and also makes the graph undirected

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

It is interesting to do the search backwards because the amount of gold is fixed at the destination, and unknown at the origin, then we can calculate the exact amount of gold and fuel required for each node going backwards.

Of course you can remove the print statement I left there

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))

Running your example

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)

Will print:

4 (6, 6)
5 (22, 8)
2 (24, 9)
3 (35, 11)

and return (35, 11). It means that for rounte from 3 to 6, it requires 11 gold, and 35 is the fuel used.