This article is made by Jason-Cow.
Welcome to reprint.
But please post the writer's address.
http://www.cnblogs.com/JasonCow/
感谢您的关注，赠送数据生成器一个
#include <ctime>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define sizen 10
#define sizem 10
#define sizew 32767
#define sizeq 20
int main(){
freopen("car.in","w",stdout);
srand(time(NULL));
int n=rand()%sizen+,m=rand()%sizem+;
cout<<n<<" "<<m<<endl;
while(m--){
int u=rand()%n+,v=rand()%n+;
if(u==v)u=(u-+n)%n+;
cout<<u<<" "<<v<<" "<<rand()%sizew+<<endl;
}
int q=rand()%sizeq+;
cout<<q<<endl;
while(q--){
int u=rand()%n+,v=rand()%n+;
if(u==v)u=(u-+n)%n;
cout<<u<<" "<<v<<endl;
}
return ;
}
似乎官方给的是倍增lca
不管了，最近练习链剖，以后有时间在补倍增的写法
就是边权下放成点权，然后树链剖分套一颗线段树就可以了
开始sb似的建成一颗大树，其实直接利用Kruskal的并查集查询是否在同一子树就好了[森林x1森林x2森林x3重要的事说三遍]
ac code 莫名压行，不压不爽
//边权的下放，可能是这题唯一的细节吧
#include <cstdio>
#include <algorithm>
#define E(u,v,w) e[++cnt]=(edge){v,w,head[u]},head[u]=cnt
using namespace std;
int GI(){
int x=,c=getchar(),f=;
while(c<''||c>''){if(c=='-')f=;c=getchar();}
while(c>=''&&c<='')x=x*+c-'',c=getchar();
return f?-x:x;
}
const int maxn=,maxm=;
struct edge{int v,w,next;}e[maxm*];
struct data{int u,v,w;}a[maxm];
int n,m,q,head[maxn],cnt,f[maxn],vis[maxn];
int find(int x){return f[x]==x?x:f[x]=find(f[x]);}
bool operator<(data x,data y){return x.w>y.w;}
void add(int u,int v,int w){E(u,v,w),E(v,u,w);}
void kruskal(){
sort(a+,a+m+);
for(int i=;i<=n;i++)f[i]=i;
for(int i=,tot=;i<=m;i++){
int u=a[i].u,v=a[i].v;
int x=find(u),y=find(v);
if(x!=y)f[x]=y,add(a[i].u,a[i].v,a[i].w),++tot;
if(tot==n-)return;
}
}
int dfn[maxn],dep[maxn],fa[maxn],top[maxn],son[maxn],rak[maxn],siz[maxn],idx,W[maxn];
void dfs1(int u,int _fa){
siz[u]=,fa[u]=_fa,dep[u]=dep[_fa]+;
for(int i=head[u];i;i=e[i].next)
if(e[i].v!=_fa){
dfs1(e[i].v,u),siz[u]+=siz[e[i].v],W[e[i].v]=e[i].w;//细节1
if(!son[u]||siz[e[i].v]>siz[son[u]])son[u]=e[i].v;
}
}
void dfs2(int u,int _top){
dfn[u]=++idx,rak[dfn[u]]=u,top[u]=_top;
if(son[u])dfs2(son[u],_top);
for(int i=head[u];i;i=e[i].next)
if(e[i].v!=fa[u]&&e[i].v!=son[u])dfs2(e[i].v,e[i].v);
}
#define ls (x<<1)
#define rs (x<<1|1)
#define mid ((l+r)>>1)
int Min[maxn<<];
void up(int x){Min[x]=min(Min[ls],Min[rs]);}
void build(int x,int l,int r){
if(l==r)Min[x]=W[rak[l]];
else build(ls,l,mid),build(rs,mid+,r),up(x);
}
int MIN(int x,int l,int r,int L,int R){
if(L>R)return <<;
if(L<=l&&r<=R)return Min[x];
if(R<=mid)return MIN(ls,l,mid,L,R);
if(L>mid)return MIN(rs,mid+,r,L,R);
return min(MIN(ls,l,mid,L,R),MIN(rs,mid+,r,L,R));
}
int jump(int x,int y){
if(find(x)!=find(y))return -;
int ans=<<;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]])swap(x,y);
ans=min(ans,MIN(,,n,dfn[top[x]],dfn[x]));
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
ans=min(ans,MIN(,,n,dfn[x]+,dfn[y]));//细节2
return ans;
}
int main(){
freopen("car.in","r",stdin);
freopen("car.out","w",stdout);
int i;n=GI(),m=GI();
for(i=;i<=m;i++)a[i].u=GI(),a[i].v=GI(),a[i].w=GI();
for(kruskal(),i=;i<=n;i++)if(!dfn[i])dfs1(i,),dfs2(i,i);
for(build(,,n),q=GI(),i=;i<=q;i++)printf("%d\n",jump(GI(),GI()));
return ;
}