标签：LCA，最大生成树，树上倍增
题目描述
A 国有 n 座城市，编号从 1 到 n，城市之间有 m 条双向道路。每一条道路对车辆都有重量限制，简称限重。现在有 q 辆货车在运输货物， 司机们想知道每辆车在不超过车辆限重的情况下，最多能运多重的货物。
输入输出格式
输入格式：
输入文件名为 truck.in。
输入文件第一行有两个用一个空格隔开的整数 n，m，表示 A 国有 n 座城市和 m 条道
路。 接下来 m 行每行 3 个整数 x、 y、 z，每两个整数之间用一个空格隔开，表示从 x 号城市到 y 号城市有一条限重为z 的道路。注意： x 不等于y，两座城市之间可能有多条道路 。
接下来一行有一个整数 q，表示有 q 辆货车需要运货。
接下来 q 行，每行两个整数 x、y，之间用一个空格隔开，表示一辆货车需要从 x 城市运输货物到 y 城市，注意： x 不等于 y 。
输出格式：
输出文件名为 truck.out。
输出共有 q 行，每行一个整数，表示对于每一辆货车，它的最大载重是多少。如果货
车不能到达目的地，输出-1。
输入输出样例
输入样例#1： 复制
4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3
输出样例#1： 复制
3
-1
3
说明
对于 30%的数据，0 < n< 1,000，0 < m < 10,000，0 < q< 1,000；
对于 60%的数据，0 < n< 1,000，0 < m < 50,000，0 < q< 1,000；
对于 100%的数据，0 < n< 10,000，0 < m < 50,000，0 < q< 30,000，0 ≤ z ≤ 100,000。
这题是在济南时晚上和zmd拼手速AC的，刺激啊，30分钟拼手速&&RP去A题
分析：先最大生成树重构树，然后对于每个询问s->t，分别查询s->LCA(s,t) 和t->LCA(s,t)路径上的最小边权。可以用树上倍增的做法记录最小边权，类似于ST表吧
话说最近模拟赛写了不少最大生成树的题，日渐变成套路。。。
Code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(register int i=a;i<=b;i++)
#define dep(i,a,b) for(register int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
using namespace std;
inline ll read()
{ll f=1,x=0;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;
}
const int maxm=5e5+6,maxn=1e5+6,inf=0x3f3f3f;
struct edge{ll u,v,w;}e[maxm];
struct redge{ll to,next,w;}re[maxm];
int head[maxn],n,m,q,fastart[maxn],depth[maxn],fa[maxn][18],d[maxn][18],cnt=0;
bool vis[maxm];
inline bool cmp(edge x,edge y){return x.w>y.w;}
inline int find(int x){return x==fastart[x]?fastart[x]:fastart[x]=find(fastart[x]);}void dfs(int x)
{vis[x]=1;rep(i,1,16){if(depth[x]<(1<<i))break;fa[x][i]=fa[fa[x][i-1]][i-1];d[x][i]=min(d[x][i-1],d[fa[x][i-1]][i-1]);}
#define reg(x) for(int i=head[x];i;i=re[i].next)reg(x){if(vis[re[i].to])continue;fa[re[i].to][0]=x;d[re[i].to][0]=re[i].w;depth[re[i].to]=depth[x]+1;dfs(re[i].to);}
}inline int lca(int x,int y)
{if(depth[x]<depth[y])swap(x,y);int t=depth[x]-depth[y];rep(i,0,16)if((1<<i)&t)x=fa[x][i];dep(i,16,0)if(fa[x][i]!=fa[y][i]){x=fa[x][i];y=fa[y][i];}if(x==y)return x;return fa[x][0];
}int ask(int x,int father)
{int re=inf,t=depth[x]-depth[father];rep(i,0,16)if((1<<i)&t){re=min(re,d[x][i]);x=fa[x][i];}return re;
}
int main()
{mem(d,inf);n=read(),m=read();rep(i,1,m)e[i].u=read(),e[i].v=read(),e[i].w=read();sort(e+1,e+1+m,cmp);rep(i,1,n)fastart[i]=i;rep(i,1,m){int r1=find(e[i].u),r2=find(e[i].v);if(r1!=r2){fastart[r1]=r2; re[++cnt]=(redge){e[i].v,head[e[i].u],e[i].w};head[e[i].u]=cnt;re[++cnt]=(redge){e[i].u,head[e[i].v],e[i].w};head[e[i].v]=cnt;}if(cnt==2*(n-1))break; }rep(i,1,n)if(!vis[i])dfs(i);q=read();rep(i,1,q){int s=read(),t=read();int r1=find(s),r2=find(t);if(r1!=r2){printf("-1\n");continue;}else {int k=lca(s,t);printf("%lld\n",min(ask(s,k),ask(t,k)));}}return 0;
}