这不是一道LCT的题目
只是一道LCA+Kruskal的题目
只是货车运输的改进版都算不上
诶，好像有点问题
#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#define N 10001#define inf 0x7fffffffusing namespace std;bool vis[N];int n,m,q,cnt,tot;int deep[N],head[N],f[N],fa[N][23],d[N][20];struct edge{ ??int x,y,v; ?}a[N<<3];struct e{ ??int next,to,v; ?}e[N<<2];void ins(int u,int v,int w){ ???e[++cnt].to=v;e[cnt].next=head[u]; ???head[u]=cnt;e[cnt].v=w;}void insert(int u,int v,int w){ ???ins(u,v,w);ins(v,u,w);}int find(int x){ ???return f[x]==x?x:f[x]=find(f[x]);}bool cmp(edge a,edge b){ ???????return a.v<b.v; } ???void dfs(int x){ ???vis[x]=1; ???for(int i=1;i<=16;i++){ ???????if(deep[x]<(1<<i))break; ???????fa[x][i]=fa[fa[x][i-1]][i-1]; ???????d[x][i]=max(d[x][i-1],d[fa[x][i-1]][i-1]); ???} ???for(int i=head[x];i;i=e[i].next){ ???????if(vis[e[i].to])continue; ???????fa[e[i].to][0]=x; ???????d[e[i].to][0]=e[i].v; ???????deep[e[i].to]=deep[x]+1; ???????dfs(e[i].to); ???}}int lca(int x,int y){ ???if(deep[x]<deep[y])swap(x,y); ???int t=deep[x]-deep[y]; ???for(int i=0;i<=16;i++) ???????if((1<<i)&t)x=fa[x][i]; ???for(int i=16;i>=0;i--) ???????if(fa[x][i]!=fa[y][i]) ???????????x=fa[x][i],y=fa[y][i]; ???return (x==y)?x:fa[x][0];}int ask(int x,int f){ ???int mn=0; ???int t=deep[x]-deep[f]; ???for(int i=0;i<=16;i++){ ???????if(t&(1<<i)){ ??????????mn=max(mn,d[x][i]); ??????????x=fa[x][i]; ???????} ???} ???return mn;}int main(){ ???scanf("%d%d",&n,&m); ???scanf("%d",&q); ???for(int i=1;i<=n;i++)f[i]=i; ????for(int i=1;i<=m;i++) ???????scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].v); ???sort(a+1,a+m+1,cmp); ???for(int i=1;i<=m;++i){ ???????int x=a[i].x,y=a[i].y; ???????int p=find(a[i].x),q=find(a[i].y); ???????if(p!=q){ ???????????f[p]=q; ???????????insert(x,y,a[i].v);++tot; ???????????if(tot==n-1)break; ???????} ???} ????for(int i=1;i<=n;++i) ???????if(!vis[i])dfs(i); ???while(q--){ ???????int x,y; ???????scanf("%d%d",&x,&y); ????????if(find(x)!=find(y)){ ???????????printf("-1\n"); ???????????continue; ???????} ???????else{ ???????????int t=lca(x,y); ???????????printf("%d\n",min(ask(x,t),ask(y,t))); ???????} ???} ???return 0;}