#include "swap.h" #include <bits/stdc++.h> using namespace std; const int N = 1e5; const int inf = 2e9; int par[N], comp_size[N], merged[N], time_valid[N], deg[N]; int find(int a) { while (par[a] != a) a = par[a]; return a; } void join(int a, int b, int time) { deg[a]++; deg[b]++; bool athree = deg[a] >= 3; bool bthree = deg[b] >= 3; a = find(a); b = find(b); if (athree) time_valid[a] = min(time_valid[a], time); if (bthree) time_valid[b] = min(time_valid[b], time); if (a == b) { time_valid[a] = min(time_valid[a], time); return; } if (comp_size[a] < comp_size[b]) swap(a, b); time_valid[a] = min(time_valid[a], max(time, time_valid[b])); par[b] = a; comp_size[a] += comp_size[b]; merged[b] = time; } void init(int n, int m, vector<int> U, vector<int> V, vector<int> W) { for (int i = 0; i < n; i++) { comp_size[i] = 1; par[i] = i; time_valid[i] = inf; merged[i] = 0; } vector<int> edges(m); iota(edges.begin(), edges.end(), 0); sort(edges.begin(), edges.end(), [&] (auto &a, auto &b) { return W[a] < W[b]; }); for (int &i: edges) { int u = U[i]; int v = V[i]; int w = W[i]; join(u, v, w); } } int getMinimumFuelCapacity(int X, int Y) { // ans is max(min(valid on path to root), max(merge on path to lca)) int merge_time = 0; int valid_time = inf; int x = X; int y = Y; while(x != y) { if (comp_size[x] > comp_size[y]) swap(x, y); merge_time = max(merge_time, merged[x]); valid_time = min(valid_time, time_valid[x]); x = par[x]; } while(merged[x] != 0) { valid_time = min(valid_time, time_valid[x]); x = par[x]; } valid_time = min(valid_time, time_valid[x]); int ans = max(valid_time, merge_time); if (ans == inf) return -1; return ans; }