unrealisticlilluson6588's blog

By unrealisticlilluson6588, history, 5 months 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.

»
5 months ago, # |
  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))$$$.

»
5 months ago, # |
  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

»
5 months ago, # |
  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