### broly_1033's blog

By broly_1033, history, 7 months ago,

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?

• 0

 » 7 months ago, # |   0 Yah you need to use heavy light decomposition, which basically uses segment tree.I hope this helps https://codeforces.cc/blog/entry/81317
•  » » 7 months ago, # ^ |   0 I have heard of HLD but couldn't seem to grasp it. Thanks, is there any other method though?
•  » » » 7 months ago, # ^ |   0 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.
•  » » » » 7 months ago, # ^ |   0 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.
•  » » » » » 9 days ago, # ^ |   0 This has a pretty good explanation of heavy light decomposition. https://blog.anudeep2011.com/heavy-light-decomposition/