传送门
这道题以前只会树剖和最小生成树+倍增。
而现在学习了一个叫做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 50005
using 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;
}