Hi everyone, I was studying how to solve query problems on trees using Euler Tour. I was wondering how to solve path query problems on trees. We can solve problems which can be solved by maintaining a prefix array (for e.g. sum of nodes in path from a to b), but how to solve say, node with maximum value in path from a to b. Can anyone guide me on this?

More specifically, sum(a, b) = sum(root, a) + sum(root, b) — 2*sum(root, lca(a, b)) + val(lca). I was using this to solve these problems using Euler Tour. But I cannot find maximum using this (CSES Path Queries 2).

Q1. Can we apply segment trees on Euler Tour array? Q2. How to solve problems like CSES Path Queries 2?

Yah you need to use heavy light decomposition, which basically uses segment tree.

I hope this helps

I have heard of HLD but couldn't seem to grasp it. Thanks, is there any other method though?

It is a fairly high level concept, if I was you I would focus on easier topics first.

No I don't think there's any other way of solving this problem.

I have covered concepts like Centroid decomposition, Euler tour. I understand why we are using these, but I cannot find a good resource for HLD.

This has a pretty good explanation of heavy light decomposition. https://blog.anudeep2011.com/heavy-light-decomposition/

My O(Nlog^2N) code is TLEing in the last test, any idea why ?

Hey! I saw your code, eventhough it is asymtotically optimal, there are few optimizations you could do. 1. You are accumulating ranges in a vector and querying the segment tree later. Instead directly query the segment tree. Avoid the intermediate list overhead. 2. This is not needed:

if (par != -1) { node.leg.erase(find(node.leg.begin(), node.leg.end(), par)); node.depth = 1 + T[par].depth; } 3. Try doing minor optimizations here and there.