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.
My O(Nlog^2N) code is TLEing in the last test, any idea why ?