Official Analysis

Binary lifting can be used to find the heaviest edge in the path from node $u$ to $v$. Therefore, we only need to find the heaviest edge from $u$ to $\text{lca}(u,v)$ and $v$ to $\text{lca}(u,v)$.

Implementation

Time Complexity: $\mathcal{O}(M\log N)$

Copy
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int MAXN = 2e5;
const int MAXL = 20;  // approximately maximum log

// for euler-tour
array<int, MAXN> enter_time, exit_time, depth;