题意:给你N个点,M条边的无向图 (N<=15000,M<=30000)第j条边的长度为 dj (1<=dj<=1e9),然后K个询问 (1<=K<=20000)。 

每个询问的格式是：A B，表示询问从A点走到B点的所有路径中，最长的边最小值是多少？

题解:求所有路径上,那些最大的边中最小的值,也就是“最小”的路径上的最大值，那也是就是最小生成树上,路径的最大值,多次询问,利用树链剖分或者倍增解决

1 #include
     
       2 using namespace std; 3 #define lld long long 4 #define N 30005 5 struct rec 6 { 7     int go,next,v; 8 }eg[N],a[N]; 9 int k,m,n,x,y,p,head[N],lca[N][22],q[N][22],dep[N]; 10 int fa[N];11 void build(int x,int y,int c)12 {13     p++;14     eg[p].next=head[x];15     eg[p].go=y;16     eg[p].v=c;17     head[x]=p;18 }19 bool cmp(rec x,rec y)20 {21     return x.v
      
       =0;i--)34         if (dep[x]-(1<
       
        =dep[y])35         {36             ret=max(ret,q[x][i]);37             x=lca[x][i];38         }39     if (x==y) return ret;40     for (int i=21;i>=0;i--)41         if (lca[x][i]!=lca[y][i])42         {43             ret=max(ret,max(q[x][i],q[y][i]));44             x=lca[x][i];45             y=lca[y][i];46         }47     ret=max(ret,max(q[x][0],q[y][0]));48     return ret;    49 }50 void dfs(int x)51 {52     for (int i=head[x];i;i=eg[i].next)53     {54         int v=eg[i].go;55         if (v==lca[x][0]) continue;56         dep[v]=dep[x]+1;57         lca[v][0]=x;58         q[v][0]=eg[i].v;59         dfs(v);60     }61 }62 int main()63 {64     freopen("1.txt","r",stdin);65     scanf("%d%d%d",&n,&m,&k);66     for (int i=1;i<=n;i++) fa[i]=i;67     for (int i=1;i<=m;i++) scanf("%d%d%d",&a[i].go,&a[i].next,&a[i].v);68     sort(a+1,a+m+1,cmp);69     int cnt=0;70     for (int i=1;i<=m;i++)71     {72         x=get(a[i].go),y=get(a[i].next);73         if (x!=y)74         {75             fa[x]=y;76             cnt++;77             build(a[i].go,a[i].next,a[i].v);78             build(a[i].next,a[i].go,a[i].v);    79         }80         if (cnt==n-1) break;81     } 82     dfs(1);83     for (int j=1;j<=21;j++)84         for (int i=1;i<=n;i++)85             if (lca[i][j-1])86             {87                 lca[i][j]=lca[lca[i][j-1]][j-1];88                 q[i][j]=max(q[i][j-1],q[lca[i][j-1]][j-1]);89             }90     while (k--)91     {92         scanf("%d%d",&x,&y);93         printf("%d\n",query(x,y));94     }    95 }