题目概述

给出一张无向图，多次询问两个点之间最长边的最小值为多少。

解题报告

因为最小生成树神奇的性质，我们只需要建出最小生成树然后求最小生成树路经上的最长边就是答案。不过我是来写Kruskal重构树的板子的233333。

Kruskal重构树是这么建的：做一遍Kruskal，但连边的时候不连 $x$ 和 $y$ ，而是连接他们并查集中的祖先 $getfa(x)$ 和 $getfa(y)$ 。

这么建能干啥？我们发现由于是按边权顺序建的，所以 $x$ 到 $y$ 的最长边一定连接着 $lca$ ，如果不是，那么说明应该在更早的时候就连通了，那这个 $lca$ 一定不是 $x$ 和 $y$ 的 $lca$ 。

如果按秩合并一下就保证树高是 $log_2n$ 了，都不用写倍增，真开心。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
#define fr first
#define sc second
const int maxn=15000,maxm=30000;
typedef pair<pair<int,int>,int> Edge;

int n,m,te,f[maxn+5],rk[maxn+5],fa[maxn+5],w[maxn+5],dep[maxn+5];Edge e[maxm+5];

inline bool cmp(const Edge &a,const Edge &b) {return a.sc<b.sc;}
int getfa(int x) {return x==f[x]?x:getfa(f[x]);}
int getdep(int x) {if (!fa[x]) return dep[x]=1;return dep[x]?dep[x]:dep[x]=getdep(fa[x])+1;}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d%d",&n,&m,&te);for (int i=1;i<=m;i++) scanf("%d%d%d",&e[i].fr.fr,&e[i].fr.sc,&e[i].sc);
    sort(e+1,e+1+m,cmp);for (int i=1;i<=n;i++) f[i]=i;
    for (int i=1;i<=m;i++){
        int x=getfa(e[i].fr.fr),y=getfa(e[i].fr.sc);if (x==y) continue;
        if (rk[x]>rk[y]) swap(x,y);f[x]=y;rk[y]+=rk[x]==rk[y];fa[x]=y;w[x]=e[i].sc;
    }for (int i=1;i<=n;i++) dep[i]=getdep(i);
    for (int x,y,ans=0;te;printf("%d\n",ans),te--,ans=0){
        scanf("%d%d",&x,&y);if (dep[x]<dep[y]) swap(x,y);
        while (dep[x]>dep[y]) ans=max(ans,w[x]),x=fa[x];
        while (x!=y) ans=max(ans,w[x]),ans=max(ans,w[y]),x=fa[x],y=fa[y];
    }
    return 0;
}