这是基于二分搜索的，这个感觉更好写，利用任何整数可以由多个2^x次方数相加得到来进行向上路径倍增。

代码和思路一样，相比较RMQ更为简单==

1 #pragma comment(linker,"/STACK:16777216") 2 #include
     
       3 #include
      
        4 #include
       
         5 using namespace std; 6 int now,head[100005],next[100005],point[100005],value[100005]; 7 int dis[100005],parent[100005][25],depth[100005]; 8 //距离根节点距离，某节点的向上走2^j的步节点，该时间深度 9 void add(int x,int y,int z)10 {11   next[++now]=head[x];12   head[x]=now;13   point[now]=y;14   value[now]=z;15 }16 void dfs(int u,int pre,int deep,int d)17 {18   dis[u]=d;19   parent[u][0]=pre;20   depth[u]=deep;21   for (int i=head[u];i;i=next[i])22   {23     int v=point[i],w=value[i];24     if (v==pre) continue;25     dfs(v,u,deep+1,d+w);26   }27 }28 void double_build(int n)29 {30   int i,j; 31   for (i=0;i+1<=20;i++)//路径倍增32     for (j=1;j<=n;j++)33       if (parent[j][i]<0) parent[j][i+1]=-1;34       else parent[j][i+1]=parent[parent[j][i]][i];35 }36 int double_query(int u,int v)37 {38   int i;39   if (depth[u]>depth[v]) swap(u,v);40   for (i=0;i<=20;i++)41     if ((depth[v]-depth[u])>>i&1)42       v=parent[v][i];43   if (u==v) return u;44   for (i=20;i>=0;i--) //二进制拆分思想达到倍增45     if (parent[u][i]!=parent[v][i])46     {47       u=parent[u][i];48       v=parent[v][i];49     }50   return parent[u][0];51 }52 int main()53 {54   int T,m,x,y,z,i,n;55   scanf("%d",&T);56   while (T--)57   {58     scanf("%d%d",&n,&m);59     now=0;60     memset(head,0,sizeof(head));61     for (i=1;i
       
      
     

题目链接：