题意：A 国有 n 座城市，编号从 1 到 n ，城市之间有 m 条双向道路。
每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物，
司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。
以1为根跑最大生成树，建图
然后以 dep[i]记录树中i的深度
f[i][j] i向上跳$2^j$步跳到的点
maxn[i][j] i到f[i][j]之间路的最小边
dfs预处理上面三个（都能处理）
然后对于询问，跑LCA对maxn取min即为ans
坑！
1、图可能不是联通的，dfs时要开个vis并循环（WA了，输出2147483647.。。。QAQ）
2、maxn处理时 maxn[i][j]=min(maxn[i][j-1],maxn[f[i][j-1]][j-1]); min里面，第一个是从i到f[i][j]的前半段，第二个是后半段
然而自己写的maxn[i][j]=min(maxn[i][j],maxn[maxn[i][j-1]][j-1]); 然后就全RE 了，怪不得。。。QAQ
3、LCA末尾，x还不是LCA，x和y的父亲才是，所以还要再取个min！！！
4、有自环。。。。。。
#include<cstdio> #include<iostream> #include<algorithm> #include<cctype> #include<cstring> using namespace std; #define love_nmr 0 #define nmr 50500 #define int long long #define olinr 10500 struct node { int to,nxt,dis; }edge[nmr]; struct like_nmr { int x,y,dis; friend bool operator < (const like_nmr &a,const like_nmr &b) { return a.dis>b.dis; } }qwq[nmr]; int head[olinr]; int cnt; int n,m,q; int tot; bool vis[olinr]; int fa[olinr]; int dep[olinr]; int f[olinr][50]; int maxn[olinr][50]; inline int read() { char ch=getchar(); int f=1,x=0; while(!isdigit(ch)) { if(ch=='-') f=-f; ch=getchar(); } while(isdigit(ch)) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } inline int findset(int x) { return x==fa[x]? fa[x]:fa[x]=findset(fa[x]); } inline void UNION(int x,int y) { fa[findset(x)]=findset(y); } inline void put(int x) { if(x<0) { putchar('-'); x=-x; } if(x>9) put(x/10); putchar(x%10+'0'); } inline void add(int from,int to,int dis) { cnt++; edge[cnt].to=to; edge[cnt].dis=dis; edge[cnt].nxt=head[from]; head[from]=cnt; } inline void dfs(int x,int fa) { vis[x]=true; dep[x]=dep[fa]+1; f[x][0]=fa; for(int i=1;(1<<i)<=dep[x];i++) { f[x][i]=f[f[x][i-1]][i-1]; maxn[x][i]=min(maxn[x][i-1],maxn[f[x][i-1]][i-1]); } for(int i=head[x];i;i=edge[i].nxt) { int go=edge[i].to; if(go==fa) continue; maxn[go][0]=min(maxn[go][0],edge[i].dis); dfs(go,x); } } inline int LCA(int x,int y) { int ans=0x7fffffff; if(dep[x]<dep[y]) swap(x,y); for(int i=30;i>=0;i--) if(dep[x]-(1<<i)>=dep[y]) { ans=min(ans,maxn[x][i]); x=f[x][i]; } if(x==y) return ans; for(int i=30;i>=0;i--) if(f[x][i]!=f[y][i]) { ans=min(ans,min(maxn[x][i],maxn[y][i])); x=f[x][i]; y=f[y][i]; } return min(ans,min(maxn[x][0],maxn[y][0])); } signed main() { ios::sync_with_stdio(false); cin>>n>>m; int x,y,z; memset(maxn,0x3f,sizeof maxn); for(int i=1;i<=n;i++) fa[i]=i; for(int i=1;i<=m;i++) cin>>qwq[i].x>>qwq[i].y>>qwq[i].dis; sort(qwq+1,qwq+m+1); for(int i=1;i<=m;i++) { if(tot==n-1) break; x=qwq[i].x; y=qwq[i].y; z=qwq[i].dis; if(findset(x)!=findset(y)) { add(x,y,z); add(y,x,z); UNION(x,y); tot++; } } for(int i=1;i<=n;i++) if(!vis[i]) dfs(i,0); cin>>q; for(int i=1;i<=q;i++) { cin>>x>>y; if(findset(x)!=findset(y)) { cout<<-1<<endl; continue; } cout<<LCA(x,y)<<endl; } return love_nmr; }