#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define ld long double
#define pii pair<int,int>
#define pdd pair<ld,ld>
#define ff first
#define ss second
#define pb push_back
#define eb emplace_back
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define fastio ios::sync_with_stdio(0),cin.tie(0);
#define nl '\n'
#define mN 200010
int dep[mN],n,m,fa[31][mN],dp[31][mN],st[31][mN];
vector<pii>g[mN];
bitset<mN>vis;
void dfs(int v){
vis[v]=1;
pii a,b;
a.ff=b.ff=-1;
a.ss=b.ss=2e9;
for(auto[u,w]:g[v]){
if(vis[u])continue;
if(a.ff==-1||a.ss>w){
b=a;
a.ff=u;
a.ss=w;
}
else if(b.ff==-1||b.ss>w){
b.ff=u;
b.ss=w;
}
}
for(auto[u,w]:g[v]){
if(vis[u])continue;
dep[u]=dep[v]+1;
fa[0][u]=v;
if(a.ff!=u)dp[0][u]=a.ss;
else dp[0][u]=b.ss;
st[0][u]=w;
dfs(u);
}
}
void init(int NN,int M,vector<int>u,vector<int>v,vector<int>w){
int i,j;
n=NN,m=M;
for(int i=0;i<m;i++){
g[u[i]].pb({v[i],w[i]});
g[v[i]].pb({u[i],w[i]});
}
fa[0][0]=N-1;
dp[0][0]=2e9;
for(i=0;i<n;i++)dp[0][i]=2e9;
for(i=0;i<n;i++)sort(all(g[i]),[](pii a,pii b){return a.ss<b.ss;});
dfs(0);
for(i=1;i<30;i++){
for(j=0;j<n;j++){
fa[i][j]=fa[i-1][fa[i-1][j]];
st[i][j]=max(st[i-1][j],st[i-1][fa[i-1][j]]);
dp[i][j]=min(dp[i-1][j],dp[i-1][fa[i-1][j]]);
}
}
}
int getMinimumFuelCapacity(int u,int v){
if(dep[u]<dep[v])swap(u,v);
int d=dep[u]-dep[v],mi=2e9,i,j,ans=0;
for(i=0;i<30;i++){
if(!d)break;
if((1<<i)&(d-1)){
ans=max(ans,st[i][u]);
mi=min(mi,dp[i][u]);
u=fa[i][u];
}
}
if(d){
ans=max(ans,st[0][u]);
if(fa[0][u]!=v)mi=min(mi,dp[0][u]);
u=fa[0][u];
}
if(u==v){
ans=max(ans,mi);
return (ans==2e9?-1:ans);
}
for(i=29;i>=0;i--){
while(fa[i][u]!=fa[i][v]){
ans=max({ans,st[i][u],st[i][v]});
mi=min({mi,dp[i][u],dp[i][v]});
u=fa[i][u];
v=fa[i][v];
}
}
ans=max({ans,st[0][u],st[0][v]});
for(auto[f,w]:g[fa[0][u]]){
if(f!=u&&f!=v){
mi=min(w,mi);
break;
}
}
ans=max(ans,mi);
return (ans==2e9?-1:ans);
}
/*
8 7
0 1 1
1 2 5
1 3 2
0 4 3
4 5 6
4 6 4
4 7 5
5
5 7
3 7
2 4
2 3
1 6
signed main(){
fastio;
}
*/
Compilation message
swap.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
swap.cpp:53:11: error: 'N' was not declared in this scope
53 | fa[0][0]=N-1;
| ^
swap.cpp: In function 'int getMinimumFuelCapacity(int, int)':
swap.cpp:68:31: warning: unused variable 'j' [-Wunused-variable]
68 | int d=dep[u]-dep[v],mi=2e9,i,j,ans=0;
| ^
