题目链接：

 

题意：找一条从 s 到 t  的路，使得瓶颈路最小。

点的数目是10^4，如果向之前的方案求 maxcost数组，O(n*n)时间是过不了的，这个时候，用到了增倍祖先。

关于倍增祖先：

我要补充的是，倍增祖先的优点，是在于倍增，他写的案例，没有体现出倍增，这里强调一下。有点像二分的思想；

 

利用倍增祖先初始化maxcost[i][j]数组，maxcost[i][j] 在倍增祖先里面表示的，结点 i 的第2^j级祖先之间的瓶颈。

用O(nlogn)初始化，然后，查询是O(logn)。

#include 
     
      using namespace std;const int maxn = 50000 + 10;const int INF = 0x3f3f3f3f;const int logmaxn = 20;int n,m;struct Edge{    int u,v,d;    bool operator < (const Edge& rhs) const    {        return d < rhs.d;    }};Edge e[maxn];int pa[maxn];int Find_Set(int x){    if(x!=pa[x])        pa[x] = Find_Set(pa[x]);    return pa[x];}vector
      
        G[maxn],C[maxn];struct LCA{    int n;    int fa[maxn];    int cost[maxn];    int L[maxn];    int anc[maxn][logmaxn];    int maxcost[maxn][logmaxn];    void preprocess()    {        for(int i=0; i
       
        =0; i--)        {            if(L[p]-(1<
        
         =L[q])            {                ans = max(ans,maxcost[p][i]);                p = anc[p][i];            }        }        if(p==q) return ans;        //lca 是 p        for(int i=log; i>=0; i--)        {            if(anc[p][i]!=-1&&anc[p][i]!=anc[q][i])            {                ans = max(ans,maxcost[p][i]);                p = anc[p][i];                ans = max(ans,maxcost[q][i]);                q = anc[q][i];            }        }        ans = max(ans,cost[p]);        ans = max(ans,cost[q]);        return ans;        //LCA 是 fa[p] = fa[q];    }};LCA solver;void dfs(int u,int fa,int level){    solver.L[u] = level;    for(int i=0; i