algorithmtreelowest-common-ancestor

Queries for minimum fuel needed to travel from U to V

Question:

Given a tree with N nodes.

Each edges of the tree contains:

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

There are 2 types of queries:

Constraints:

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

Example:

N = 6, G = 2

example image

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.

Solution

  • 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

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