emmmm一开始是想到网络流来着？？？（最大流嘛233）
然后发现自己好像已经差不多忘完了？？？
于是打开题解，ctrl+f，输入网络流，好像没有题解，于是就老老实实想正解去了。
正解：
多组询问，想想网络流也要T（EK本来就慢，其它就不说了），所以一定是还有更简单的方法的！！！
对于每一个点（或者说路径），只有最小的那个边才对答案有影响（不是吗？）
慢着！这不是.....最小生成树？
于是就建最小生成树然后LCA。。。。。
于是愉快地选择kruskal和倍增lca。
于是这题就没什么了
代码：
#include<bits/stdc++.h> using namespace std; const int maxn=500005; int m,n,fat[maxn]; struct node { int x,y,z; }a[maxn]; struct edge { int next,to,dis; }e[maxn<<1]; int head[maxn],cnt,vis[maxn]; inline void addedge(int from,int to,int dis) { e[++cnt].next=head[from]; e[cnt].to=to; e[cnt].dis=dis; head[from]=cnt; } bool cmp(node x,node y) { return x.z>y.z; } int find(int x) { return fat[x]==x?x:fat[x]=find(fat[x]); } void kruskal() { for(int i=1;i<=n;i++) fat[i]=i; for(int i=1;i<m;i++) { int fa=find(a[i].x); int fb=find(a[i].y); if(fa!=fb) { fat[fa]=fb; addedge(a[i].x,a[i].y,a[i].z); addedge(a[i].y,a[i].x,a[i].z); } } } int dep[maxn],f[25][maxn],w[25][maxn]; void dfs(int u,int deep)//预处理lca { vis[u]=1; dep[u]=deep; for(int i=head[u];i;i=e[i].next) { int v=e[i].to; if(dep[v]!=0) continue; dfs(v,deep+1); f[0][v]=u; w[0][v]=e[i].dis; } } int lca(int a,int b)//lca { if(find(a)!=find(b)) return -1;//不连通 int ans=99999999; if(dep[a]<dep[b]) swap(a,b); for(int i=20;i>=0;i--) { if(dep[b]<=dep[a]-(1<<i)) { ans=min(ans,w[i][a]); a=f[i][a]; } } if(a==b) return ans; for(int i=20;i>=0;i--) { if(f[i][a]!=f[i][b]) { ans=min(ans,min(w[i][a],w[i][b])); a=f[i][a]; b=f[i][b]; } } ans=min(ans,min(w[0][a],w[0][b])); //printf("%d ",ans); return ans; } int main() { //freopen("testdata.in","r",stdin); //freopen("1.out","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z); sort(a+1,a+m+1,cmp); kruskal(); for(int i=1;i<=n;i++) { if(vis[i]) continue; dfs(i,1); f[0][i]=i; w[0][i]=99999999; } for(int i=1;(1<<i)<=n;i++) { for(int j=1;j<=n;j++) { f[i][j]=f[i-1][f[i-1][j]]; w[i][j]=min(w[i-1][j],w[i-1][f[i-1][j]]); } } int q; scanf("%d",&q); for(int i=1;i<=q;i++) { int x,y; scanf("%d%d",&x,&y); printf("%d ",lca(x,y)); } return 0; }
（完）