Path Queries 2 on CSES

Revision en1, by broly_1033, 2022-01-15 10:21:49

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?

Tags euler tour, segment tree, cses_helpline


  Rev. Lang. By When Δ Comment
en1 English broly_1033 2022-01-15 10:21:49 714 Initial revision (published)