标签：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;
}
