这道题以前只会树剖和最小生成树+倍增。
而现在学习了一个叫做kruskal” role=”presentation” style=”position: relative;”>kruskalkruskal重构树的优美姿势，搞得我不想写都不行了。
好吧事实上krsukal” role=”presentation” style=”position: relative;”>krsukalkrsukal重构树上两点的lca” role=”presentation” style=”position: relative;”>lcalca就是它们路径上的瓶颈这个优美的性质可以秒杀这道题。
代码如下：
#include<bits/stdc++.h>#define N 10005#define M 50005using namespace std;inline int read(){ int ans=0; char ch=getchar(); while(!isdigit(ch))ch=getchar(); while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar(); return ans;}inline void write(int x){ if(x>0)write(x/10); putchar((x%10)^48);}int n,m,q,fa[N<<1],son[N<<1][2],w[N<<1],pa[N<<1][20],dep[N<<1];bool vis[N<<1];inline int find(int x){return x==fa[x]?fa[x]:fa[x]=find(fa[x]);}struct Node{int u,v,w;}e[M];inline bool cmp(Node a,Node b){return a.w>b.w;}inline void dfs(int p){ for(int i=1;i<=19;++i)pa[p][i]=pa[pa[p][i-1]][i-1]; vis[p]=true; if(!son[p][0]&&!son[p][1])return; dep[son[p][0]]=dep[son[p][1]]=dep[p]+1; dfs(son[p][0]),dfs(son[p][1]);}inline void kruskal(){ sort(e+1,e+m+1,cmp); int cnt=n; memset(vis,false,sizeof(vis)); for(int i=1;i<=(n<<1);++i)fa[i]=i; for(int i=1;i<=m;++i){ int x=find(e[i].u),y=find(e[i].v); if(x!=y){ pa[x][0]=pa[y][0]=fa[x]=fa[y]=++cnt; son[cnt][0]=x,son[cnt][1]=y; w[cnt]=e[i].w; } } for(int i=cnt;i>=1;--i)if(!vis[i])dfs(i);}inline int lca(int x,int y){ if(dep[x]<dep[y])swap(x,y); for(int i=19;i>=0;--i){ if(dep[pa[x][i]]>=dep[y])x=pa[x][i]; if(x==y)return x; } for(int i=19;i>=0;--i)if(pa[x][i]!=pa[y][i])x=pa[x][i],y=pa[y][i]; return pa[x][0];}int main(){ n=read(),m=read(); for(int i=1;i<=m;++i)e[i].u=read(),e[i].v=read(),e[i].w=read(); kruskal(); q=read(); while(q--){ int u=read(),v=read(),x=find(u),y=find(v); if(x!=y){puts("-1");continue;} printf("%d\n",w[lca(u,v)]); } return 0;}
