Блог пользователя unrealisticlilluson6588

Автор unrealisticlilluson6588, история, 5 месяцев назад, По-английски

https://www.interviewbit.com/problems/max-edge-queries/

Someone please suggest a idea or share some resource that will help me to solve this problem.

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

You need standart LCA. For each vertex $$$a$$$ you can calculate $$$find(a, count)$$$ — the maximum weigth of $$$count$$$ edges if you go from $$$a$$$ up to the root. So if you know that $$$LCA(x, y) = z$$$ and $$$dist(x, z) = l, dist(y, z) = r$$$, the answer is $$$max(find(x, l), find(y, r))$$$.

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

you can solve queries offline using some precomputation

overview of soln

resources LCA segment tree

»
5 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Precompute binary lifting, and compute like a sparse table on the tree, for each node U, calculate the maximal edge 2^i up, then for each query compute the LCA, and compute the maximum from u -> LCA and from v -> LCA