传送门：https://www.luogu.org/problem/show?pid=1967
题目描述
A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。
输入格式
输入文件第一行有两个用一个空格隔开的整数 n，m，表示 A 国有 n 座城市和 m 条道
路。 接下来 m 行每行 3 个整数 x、 y、 z，每两个整数之间用一个空格隔开，表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意： x 不等于 y，两座城市之间可能有多条道路 。
接下来一行有一个整数 q，表示有 q 辆货车需要运货。
接下来 q 行，每行两个整数 x、y，之间用一个空格隔开，表示一辆货车需要从 x 城市运输货物到 y 城市，注意： x 不等于 y 。
输出格式
输出共有 q 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货
车不能到达目的地，输出-1。
样例君
输入
4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3
输出
3
-1
3
说明
对于 30%的数据，0 < n < 1,000，0 < m < 10,000，0 < q< 1,000；
对于 60%的数据，0 < n < 1,000，0 < m < 50,000，0 < q< 1,000；
对于 100%的数据，0 < n < 10,000，0 < m < 50,000，0 < q< 30,000，0 ≤ z ≤ 100,000。
蒟蒻吐槽
这道题的数据很良心，考试的时候，不会写树上倍增的我，无奈写了个树上增（逃，居然A了，洛谷上也一样，害怕。
这道题其实就是最大生成树之后，然后求两点间路径上最小的权值，所以跑最大生成树。在询问的时候提前看一下两个点联不联通就可以了。
我会附上我的两个代码，一个是很迷醉的树上增，一个是蒟蒻学习了树上倍增之后写的树上倍增版本的。关于树上倍增版本的蒟蒻建议可以去百度一下hzwdalao的网站，传送门：http://hzwer.com/1344.html
代码
树上增（手动滑稽）
#include<cstdio> #include<algorithm> using namespace std; const int N=10010; const int M=50010; const int inf=2147483647; struct edge { int to,last,lon; }a[M],e[M*2]; int fa[N],faa[N],dis[N],dep[N],n,m,fax,fay; int head[N],cnt; bool cmp(edge _,edge __) { return _.lon>__.lon; } inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } inline int find(int _) { if(_==fa[_])return _; return fa[_]=find(fa[_]); } inline void add(int u,int v,int x) { cnt++; e[cnt].to=v; e[cnt].lon=x; e[cnt].last=head[u]; head[u]=cnt; } void dfs(int u,int dp,int fa1) { faa[u]=fa1;dep[u]=dp; for(int i=head[u];i;i=e[i].last) { int v=e[i].to; if(v!=fa1) { dfs(v,dp+1,u); dis[v]=e[i].lon; } } } int work(int u,int v) { int ans=inf; if(dep[u]>dep[v])swap(u,v); while(dep[v]>dep[u]) { ans=min(ans,dis[v]); v=faa[v]; } while(faa[u]!=faa[v]) { ans=min(ans,min(dis[u],dis[v])); u=faa[u];v=faa[v]; } if(u!=v)ans=min(ans,min(dis[u],dis[v])); printf("%d ",ans); } int main() { freopen("truck.in","r",stdin); freopen("truck.out","w",stdout); int x,y,z,ct=0,q; n=read();m=read(); for(int i=1;i<=n;++i) fa[i]=i; for(int i=1;i<=m;++i) { x=read();y=read();z=read(); a[i].last=x;a[i].to=y;a[i].lon=z; } sort(a+1,a+m+1,cmp); for(int i=1;i<=m;++i) { fax=find(a[i].last);fay=find(a[i].to); if(fax!=fay) { ct++; fa[fay]=fax; add(a[i].last,a[i].to,a[i].lon); add(a[i].to,a[i].last,a[i].lon); } if(ct==n-1)break; } for(int i=1;i<=n;++i) { if(fa[i]==i)dfs(i,0,i); } q=read(); while(q--) { x=read();y=read(); fax=find(x);fay=find(y); if(fax!=fay){printf("-1 ");continue;} work(x,y); } return 0; }
树上倍增
#include<cstdio> #include<algorithm> using namespace std; const int N=10010; const int M=50010; const int inf=2147483647; struct edge { int to,last,lon; }a[M],e[M*2]; int cnt,head[N],faa[N],n,m; int fa[N][20],dis[N][20],vis[N],fax,fay,dep[N]; bool cmp(edge _,edge __) { return _.lon>__.lon; } inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } inline void add(int u,int v,int x) { cnt++; e[cnt]=(edge){v,head[u],x}; head[u]=cnt; } inline int find(int _) { if(_==faa[_])return _; return faa[_]=find(faa[_]); } void kruskal() { int ct=0; for(int i=1;i<=n;++i) faa[i]=i; sort(a+1,a+m+1,cmp); for(int i=1;i<=m;++i) { fax=find(a[i].last);fay=find(a[i].to); if(fax==fay)continue; faa[fay]=fax; ct++; add(a[i].last,a[i].to,a[i].lon); add(a[i].to,a[i].last,a[i].lon); if(ct==n-1)break; } } void dfs(int u) { vis[u]=1; for(int i=1;i<=16;++i) { if(dep[u]<(1<<i))break; fa[u][i]=fa[fa[u][i-1]][i-1]; dis[u][i]=min(dis[u][i-1],dis[fa[u][i-1]][i-1]); } for(int i=head[u];i;i=e[i].last) { int v=e[i].to; if(vis[v])continue; dep[v]=dep[u]+1; fa[v][0]=u; dis[v][0]=e[i].lon; dfs(v); } return; } int lca(int u,int v) { if(dep[u]>dep[v])swap(u,v); int ch=dep[v]-dep[u],ans=inf; for(int i=16;i>=0;--i) if(ch&(1<<i)) { ans=min(ans,dis[v][i]); v=fa[v][i]; } if(u==v)return ans; for(int i=16;i>=0;--i) if(fa[u][i]!=fa[v][i]) { ans=min(ans,min(dis[u][i],dis[v][i])); u=fa[u][i];v=fa[v][i]; } if(fa[u][0]==v)return ans; return min(ans,min(dis[u][0],dis[v][0])); } int main() { int q,x,y; n=read();m=read(); for(int i=1;i<=m;++i) { a[i].last=read(); a[i].to=read(); a[i].lon=read(); } kruskal(); for(int i=1;i<=n;++i) if(!vis[i])dfs(i); q=read(); while(q--) { x=read();y=read(); fax=find(x);fay=find(y); if(fax!=fay){printf("-1 ");continue;} printf("%d ",lca(x,y)); } return 0; }