### broly_1033's blog

By broly_1033, history, 17 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

 » 17 months ago, # |   0 Yah you need to use heavy light decomposition, which basically uses segment tree.I hope this helps https://codeforces.com/blog/entry/81317
•  » » 17 months ago, # ^ |   0 I have heard of HLD but couldn't seem to grasp it. Thanks, is there any other method though?
•  » » » 17 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.
•  » » » » 17 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.
•  » » » » » 10 months ago, # ^ |   0 This has a pretty good explanation of heavy light decomposition. https://blog.anudeep2011.com/heavy-light-decomposition/
 » 7 weeks ago, # |   0 My O(Nlog^2N) code is TLEing in the last test, any idea why ?
•  » » 3 days ago, # ^ | ← Rev. 2 →   0 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; opacity: 0.5; } .ComplaintFrame a:hover { opacity: 1; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup input[type=submit] { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } 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.