### unrealisticlilluson6588's blog

By unrealisticlilluson6588, history, 4 weeks ago,

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.

 » 4 weeks ago, # |   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))$.
 » 4 weeks ago, # |   0 you can solve queries offline using some precomputation overview of solnfirst calculate $LCA(u, v) = L$ for each $query$ calculate the max edge between each $(L, u)$ and $(L, v)$ pair you can do this in $O(n + q*log(n))$ using segment tree best i know, may be there is a better way to this after doing above two steps you know the $ans$ for $(L, u)$ and $(L, v)$ $ans$ for query $(u, v)$ is $max(ans(L, u), ans(L, v))$ resources LCA segment tree
 » 4 weeks ago, # |   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