#include "swap.h" #include <bits/stdc++.h> using namespace std; static const int MAXN = 100000; static const int LOG = 17; vector<pair<int,int>> adj[MAXN]; int up[MAXN][LOG]; int mx[MAXN][LOG]; int depth[MAXN]; int parent[MAXN]; int n_global; struct Edge { int u, v, w; }; int find_set(int v) { return parent[v] == v ? v : parent[v] = find_set(parent[v]); } void dfs(int v, int p, int w) { up[v][0] = p; mx[v][0] = w; for (int i = 1; i < LOG; i++) { up[v][i] = up[ up[v][i-1] ][i-1]; mx[v][i] = max(mx[v][i-1], mx[ up[v][i-1] ][i-1]); } for (auto [to, wt] : adj[v]) { if (to == p) continue; depth[to] = depth[v] + 1; dfs(to, v, wt); } } void init(int N, int M, vector<int> U, vector<int> V, vector<int> W) { n_global = N; vector<Edge> edges; for (int i = 0; i < M; i++) { edges.push_back({U[i], V[i], W[i]}); } for (int i = 0; i < N; i++) { parent[i] = i; adj[i].clear(); } sort(edges.begin(), edges.end(), [](const Edge &a, const Edge &b) { return a.w < b.w; }); // Build MST for (auto &e : edges) { int a = find_set(e.u); int b = find_set(e.v); if (a != b) { parent[a] = b; adj[e.u].push_back({e.v, e.w}); adj[e.v].push_back({e.u, e.w}); } } depth[0] = 0; dfs(0, 0, 0); } int getMinimumFuelCapacity(int X, int Y) { int u = X; int v = Y; int ans = 0; if (depth[u] < depth[v]) swap(u, v); // Lift u up for (int i = LOG - 1; i >= 0; i--) { if (depth[u] - (1 << i) >= depth[v]) { ans = max(ans, mx[u][i]); u = up[u][i]; } } if (u == v) return ans; // Lift both for (int i = LOG - 1; i >= 0; i--) { if (up[u][i] != up[v][i]) { ans = max(ans, mx[u][i]); ans = max(ans, mx[v][i]); u = up[u][i]; v = up[v][i]; } } // One step to LCA ans = max(ans, mx[u][0]); ans = max(ans, mx[v][0]); return ans; }