broly_1033's blog

Path Queries 2 on CSES
By broly_1033, history, 4 years ago, In English

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?

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
4 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

I hope this helps

https://mirror.codeforces.com/blog/entry/81317

→ Reply
  • »
    »
    4 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      4 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply