题目大意

多次询问从A到B的所有路径上的一条使得其最小边权最大。


首先这条路一定在最大生成树上。因为只有这样才能防止有更优解。

想到这个这就是SB题了,跑个Kruskal+LCA就可以了……

我把fai的i和j弄反了是什么鬼= =

#include <cstdio>
#include <algorithm>
using namespace std;
struct edge{int u,v,l;} e[50010];
int n,m,q,depth[10010],fa[10010][21],dis[10010][21],fat[10010],blk[10010],cnt,tos,inx,iny;
int to[100010],nex[100010],val[100010],head[10010],tot;
bool cmp(edge tx,edge ty) {return tx.l>ty.l;}
void addedge(int tx,int ty,int tz) {to[++tot]=ty,nex[tot]=head[tx],head[tx]=tot,val[tot]=tz;}
int unifind(int tx) {return fat[tx]==tx?tx:fat[tx]=unifind(fat[tx]);}
int unifindb(int tx) {return blk[tx]==tx?tx:blk[tx]=unifindb(blk[tx]);}
void kruskal()
{
    for(int i=1;i<=n;++i) fat[i]=i;
    for(int i=1;i<=m;++i)
    {
        int tx=unifind(e[i].u),ty=unifind(e[i].v);
        if(tx!=ty)
        {
            ++cnt;
            fat[tx]=ty;
            addedge(e[i].u,e[i].v,e[i].l);
            addedge(e[i].v,e[i].u,e[i].l);
            if(cnt==tos) break;
        }
    }
    return;
}
void dfs(int pos)
{
    for(int i=head[pos];i;i=nex[i])
        if(!depth[to[i]])
        {
            depth[to[i]]=depth[pos]+1;
            fa[to[i]][0]=pos;
            dis[to[i]][0]=val[i];
            dfs(to[i]);
        }
    return;
}
void init()
{
    for(int i=1;i<=20;++i)
        for(int j=1;j<=n;++j)
        {
            fa[j][i]=fa[fa[j][i-1]][i-1];
            dis[j][i]=min(dis[j][i-1],dis[fa[j][i-1]][i-1]);
        }
    return;
}
int query(int tx,int ty)
{
    int ret=0x3f3f3f3f;
    if(depth[tx]<depth[ty]) swap(tx,ty);
    for(int i=20;~i;i--)
        if(depth[fa[tx][i]]>=depth[ty]) ret=min(ret,dis[tx][i]),tx=fa[tx][i];
    for(int i=20;~i;i--)
        if(fa[tx][i]!=fa[ty][i]) ret=min(ret,min(dis[tx][i],dis[ty][i])),tx=fa[tx][i],ty=fa[ty][i];
    return tx==ty?ret:min(ret,min(dis[tx][0],dis[ty][0]));
}
int main()
{
    scanf("%d%d",&n,&m);
    tos=n;
    for(int i=1;i<=n;++i) blk[i]=i;
    for(int i=1;i<=m;++i) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].l),blk[unifindb(e[i].u)]=unifindb(e[i].v);
    for(int i=1;i<=n;++i) if(blk[i]==i) tos--;
    sort(e+1,e+m+1,cmp);
    kruskal();
    depth[1]=1;
    dfs(1);
    init();
    scanf("%d",&q);
    while(q--)
    {
        scanf("%d%d",&inx,&iny);
        if(unifindb(inx)!=unifindb(iny)) printf("-1\n");
        else printf("%d\n",query(inx,iny));
    }
    return 0;
}