货车运输 vijos 1843 NOIP2013 D1T3 最大生成树，并查集，（伪·LCA）

（本人比较笨，没写LCA，在树上暴力跑过了此题。）

可以证明答案一定在最大生成树上，因为如果答案比最大生成树上的路径更优，那么最大生成树一定不是正确的。反证之。

同时注意到最大生成树过程中是使用了并查集的，所以不会出现某些点“被丢下”的情况，希望读者不必在此纠结。

我们跑完最大生成树之后，已经有了一个并查集，我们用并查集来判断两个点是否联通，若两个点不在一个并查集中，那么他们也一定在原图中不联通，直接输出-1即可。

首先记录X到树根路径上每个点的“路径最大限重”，再用y向根跑，若遇到有记录的节点，就取x的记录和y跑的记录的最小值，输出即可。

附上AC代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
using namespace std;
template<class T> inline void read(T &_a){
    bool f=0;int _ch=getchar();_a=0;
    while(_ch<'0' || _ch>'9'){if(_ch=='-')f=1;_ch=getchar();}
    while(_ch>='0' && _ch<='9'){_a=(_a<<1)+(_a<<3)+_ch-'0';_ch=getchar();}
    if(f)_a=-_a;
}

const int maxn=10001,maxm=50001;
int n,m,egcnt,head[maxn],Q,egcnttt,belong[maxn],fa[maxn],tmp[maxn];
bool vis[maxn];
struct edge {int to,next,dis;}w[maxn<<1];
struct edge2{
    int from,to,dis;
    inline bool operator < (const edge2 x) const {return dis>x.dis;}
}edg[maxm];

inline void addedge2(int from,int to,int dis)
{
    edg[++egcnttt].to=to;
    edg[egcnttt].from=from;
    edg[egcnttt].dis=dis;
}

inline void addedge(int from,int to,int dis)
{
    w[++egcnt].to=to;
    w[egcnt].next=head[from];
    w[egcnt].dis=dis;
    head[from]=egcnt;
    w[++egcnt].to=from;
    w[egcnt].next=head[to];
    w[egcnt].dis=dis;
    head[to]=egcnt;
}

int find(int u)
{ return belong[u]==u?u:belong[u]=find(belong[u]); }

inline void kruskal()
{
    sort(edg+1,edg+egcnttt+1);
    for (register int i=1;i<=n;++i) belong[i]=i;
    for (register int i=1;i<=egcnttt&&egcnt<((n-1)<<1);++i)
    {
        int a1=find(edg[i].from);
        int a2=find(edg[i].to);
        if(a1!=a2)
        {
            belong[a1]=a2;
            addedge(edg[i].from,edg[i].to,edg[i].dis);
        }
    }
}

void dfs_fa(int u)
{
    for (register int i=head[u];i;i=w[i].next)
        if(!fa[w[i].to]) fa[w[i].to]=u,dfs_fa(w[i].to);
}

inline int solve(int x,int y)
{
    if(!fa[x]) fa[x]=-1,dfs_fa(x);
    memset(tmp,0x7f,sizeof(tmp));
    tmp[x]=10000000;
    while(x!=-1)
    {
        for (register int i=head[x];i;i=w[i].next)
        if(w[i].to==fa[x])
        {
            tmp[w[i].to]=min(w[i].dis,tmp[x]);
            break;
        }
        x=fa[x];
    }
    int ans=10000000;
    while(y!=-1)
    {
        if(tmp[y]<=10000000) {ans=min(ans,tmp[y]); break;}
        for (register int i=head[y];i;i=w[i].next)
        if(w[i].to==fa[y])
        {
            ans=min(w[i].dis,ans);
            break;
        }
        y=fa[y];
    }
    return ans;
}

int main()
{
    read(n); read(m);
    for (register int i=1,x,y,z;i<=m;++i) read(x),read(y),read(z),addedge2(x,y,z);
    kruskal();
    for (read(Q);Q;--Q)
    {
        int x,y;
        read(x); read(y);
        int a1=find(x);
        int a2=find(y);
        if(a1!=a2) {printf("-1\n"); continue;}
        printf("%d\n",solve(x,y));
    }
    return 0;
}