LCA

const int N = ${1:5e5} + 5;
vector<int> adj[N];
int siz[N], ms[N], dep[N], top[N], p[N];

void dfs1(int now, int fa) {
  siz[now] = 1;
  ms[now] = -1;
  dep[now] = dep[fa] + 1;
  p[now] = fa;
  for (auto t : adj[now]) {
    if (t == fa) continue;
    dfs1(t, now);
    siz[now] += siz[t];
    if (ms[now] == -1 || siz[t] > siz[ms[now]]) ms[now] = t;
  }
}

void dfs(int now, int fa, int tag) {
  top[now] = tag;
  if (ms[now] != -1) {
    dfs(ms[now], now, tag);
  }
  for (auto t : adj[now]) {
    if (t == fa || t == ms[now]) continue;
    dfs(t, now, t);
  }
}

int LCA(int a, int b) {
  while (top[a] != top[b]) {
    if (dep[top[a]] < dep[top[b]]) {
      b = p[top[b]];
    } else {
      a = p[top[a]];
    }
  }
  return dep[a] > dep[b] ? b : a;
}

// 倍增法求 LCA，顺便维护了路径上最大边权
vector d(n + 1, vector<pair<int, int>>(20));
vector<int> dep(n + 1);
auto dfs = [&](auto self, int u, int fa) -> void {
  dep[u] = dep[fa] + 1;
  for (auto [v, w] : adj[u]) {
    if (v == fa) continue;
    d[v][0] = {u, w};
    self(self, v, u);
  }
};
dfs(dfs, 1, 0);
for (int i = 1; i < 20; i++) {
  for (int j = 1; j <= n; j++) {
    d[j][i] = {d[d[j][i - 1].first][i - 1].first, max(d[j][i - 1].second, d[d[j][i - 1].first][i - 1].second)};
  }
}

auto dis = [&](int u, int v) {
  int res = 0;
  if (dep[u] < dep[v]) swap(u, v);
  for (int i = 19; i >= 0; i--) {
    if (dep[d[u][i].first] >= dep[v]) {
      res = max(res, d[u][i].second);
      u = d[u][i].first;
    }
  }
  assert(dep[u] == dep[v]);
  if (u == v) {
    return res;
  }
  for (int i = 19; i >= 0; i--) {
    if (d[u][i].first != d[v][i].first) {
      res = max(res, d[u][i].second);
      res = max(res, d[v][i].second);
      u = d[u][i].first;
      v = d[v][i].first;
    }
  }
  res = max(res, d[u][0].second);
  res = max(res, d[v][0].second);
  return res;
};