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.
| # | User | Rating |
|---|---|---|
| 1 | jiangly | 3810 |
| 2 | Benq | 3676 |
| 3 | Kevin114514 | 3655 |
| 4 | maroonrk | 3463 |
| 5 | strapple | 3447 |
| 6 | Um_nik | 3387 |
| 7 | heuristica | 3322 |
| 8 | turmax | 3317 |
| 9 | tourist | 3307 |
| 10 | jiangbowen | 3291 |
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 156 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | Um_nik | 142 |
| 5 | Errichto | 139 |
| 6 | adamant | 137 |
| 7 | AmShZ | 135 |
| 8 | BledDest | 132 |
| 8 | maroonrk | 132 |
| 10 | qwexd | 129 |
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.
| Name |
|---|



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))$$$.
you can solve queries offline using some precomputation
first 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
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