Home1ander's blog

By Home1ander, history, 2 years ago, In English

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.

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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))$$$.

»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

you can solve queries offline using some precomputation

overview of soln

resources LCA segment tree

»
2 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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