超级详细倍增法实现 LCA

全栈程序员-站长 • 2022年4月9日上午6:20 • 未分类 • 阅读 47

描述：倍增法用于很多算法当中，通过字面意思来理解就是翻倍增加嘛，这里着重讲使用倍增法在树中的应用求LCA；LCA是啥呢在一棵树当中 lca表示的是两个节点最近公共祖先，大家看这课树哈节点5，3的lca就是1，13和11的LCA就是6。节点8,12的lca就是8，那么我们如何通过被增来实现LCA呢。首先大家看下这个数组grand[x][i],这个数组表示标号为x节

大家好，又见面了，我是你们的朋友全栈君。

描述：倍增法用于很多算法当中，通过字面意思来理解就是翻倍增加嘛，这里着重讲使用倍增法在树中的应用求LCA；

超级详细倍增法实现 LCA

LCA是啥呢在一棵树当中 lca表示的是两个节点最近公共祖先，大家看这课树哈节点5 ，3的lca就是1，13和11的LCA就是6。节点8,12的lca就是8，那么我们如何通过被增来实现LCA呢。

首先请大家认真看下面的分析。

depth[x],表示x节点的深度。

大家看下这个数组 grand[x][i] ,这个数组表示标号为x节点向上跳2^i步的节点。例如grand[5][0]=2，因为5这个节点向上跳2^0次方个就是2，当然所有节点向上跳一个就是他的父亲节点，

得到grand[x][0]=他的爸爸吐舌头，

那grand[x][1]=什么呢？等于grand[grand[x][0]][0];

既grand[x][i]=grand[grand[x][i-1]][i-1],为什么呢，2^4=2^3+2^3,表示 x向上跳2的i次的节点=x向上跳i-1次方的这个节点向上跳i-1次方，有点绕口。例如 grand[13][2]=grand[6][2]=g[g[rand][i-1]][i-1];

有了这个预处理那我们是不是可以得到每一个节点向上跳i格呢，然后就是i的取值范围为1<=i<=log2(n),向下取整n表示节点个数，也就是说grand[x][log2(n)]就至少可以跳到根节点甚至上面，当然上面啥都没有。

我们这里还有一个数组 gw[x][i],表示x节点向上跳2^i次方的距离（权）。同样的有gw[x][i]=gw[x][i-1]+gw[grand[x][i-1]][i-1],这个公式表示x到他向上跳2的i次方那个节点的距离=x跳2^i-1次方的距离加上，他向上跳2^i-1次方这个点到他上面跳2^i-1次方的距离。

例如1,3,6,10,13，他们之间的边的权等于 2 4 3 6,既gw[13][0]=他爸爸10到他的距离等于6，gw[]13[2]=gw[13][1]+gw[6][1];。

其实我们可以自己加很多类似的数组

例如max[x][i]啊表示 x向上跳2^i次方的边的最大的那条边。这里就不一一举例子子了

现在有了这些预处理。我下面是用dfs实现的预处理；

就看如何实现LCA了吧，

首先给定两个节点。假如给定的是a=13，b=12.。要我们求他们的lca ，首先第一步我们要把他们调整到同一深度，既把a向上跳一个步这样他们的深度就相同的了。我们是把深度高的向上调。调整跟深度低的一样。

然后就两个节点一起向上跳一个2^j，首先我们j从log2(n)=3开始跳，跳到0。我们要跳到他们lca的下面两个节点。既3和4，既可以跳的节点是他们不相同并且不超出根节点(grand[a][j]!=grand[b][j])，这里是j=1的时候跳了，j=1因为(grand[a][j]!=grand[b][j]);就执行（a=grand[a][j],b=grand[b][j]）a就跳到了3,b就跳到了4，其余的j就不可以跳因为j=3，2就到根的上面了j=0他们就想等了。跳到那，最后退出，grand[a][0]就是他们的lca了。

这就是程序的执行过程。下面看代码

模板体：hdu2586

代码：

#include<stdio.h>
#include<string.h>
#include<vector>
#include<stdlib.h>
#include<math.h>
#define max 40001
#define maxl 25
using namespace std;
typedef struct
{
    int from,to,w;
}edge;//这个结构体用来存储边

vector<edge>edges;
vector<int> G[max];
//保存边的数组
int grand[max][maxl],gw[max][maxl];//x向上跳2^i次方的节点，x到他上面祖先2^i次方的距离
int depth[max];//深度
int n,m,N;
void addedge(int x,int y,int w)//把边保存起来的函数
{
   edge a={x,y,w},b={y,x,w};
   edges.push_back(a);
   edges.push_back(b);

   G[x].push_back(edges.size()-2);
   G[y].push_back(edges.size()-1);
}
void dfs(int x)//dfs建图
{
    for(int i=1;i<=N;i++)//第一个几点就全部都是0咯，第二个节点就有变化了，不理解的话建议复制代码输出下这些数组

    {
        grand[x][i]=grand[grand[x][i-1]][i-1];
        gw[x][i]=gw[x][i-1]+gw[grand[x][i-1]][i-1];
       // if(grand[x][i]==0) break;
    }

    for(int i=0;i<G[x].size();i++)
    {   edge  e = edges[G[x][i]];
         if(e.to!=grand[x][0])//这里我们保存的是双向边所以与他相连的边不是他父亲就是他儿子父亲的话就不能执行，不然就死循环了。

           {
                depth[e.to]=depth[x]+1;//他儿子的深度等于他爸爸的加1
                grand[e.to][0]=x;//与x相连那个节点的父亲等于x
                gw[e.to][0]=e.w;//与x相连那个节点的距离等于这条边的距离
                dfs(e.to);//深搜往下面建
           }
    }
}
void Init(){
    //n为节点个数
    N = floor(log(n + 0.0) / log(2.0));//最多能跳的2^i祖先
    depth[1]=0;//根结点的祖先不存在，用-1表示
    memset(grand,0,sizeof(grand));
    memset(gw,0,sizeof(gw));
    dfs(1);//以1为根节点建树

}
int lca(int a,int b)
{ if(depth[a] > depth[b]) swap(a, b);//保证a在b上面，便于计算
    int ans = 0;
    for(int i = N; i >= 0; i--) //类似于二进制拆分，从大到小尝试
        if(depth[a] < depth[b] && depth[grand[b][i]] >= depth[a])//a在b下面且b向上跳后不会到a上面
            ans +=gw[b][i], b=grand[b][i];//先把深度较大的b往上跳

    for(int j=N;j>=0;j--)//在同一高度了,他们一起向上跳,跳他们不相同节点，当全都跳完之后grand【a】【0】就是lca,上面有解释哈。
    {
        if(grand[a][j]!=grand[b][j])
        {   ans+=gw[a][j];
            ans+=gw[b][j];
            a=grand[a][j];
            b=grand[b][j];

        }
    }
    if(a!=b)//a等于b的情况就是上面土色字体的那种情况
    {
        ans+=gw[a][0],ans+=gw[b][0];
    }
    return ans;
}
int main()
{ int t ;
  scanf("%d",&t);
  while(t--)
  {   scanf("%d%d",&n,&m);
      for(int i=1;i<n;i++)
      {
          int x,y,w;
          scanf("%d%d%d",&x,&y,&w);
          addedge(x,y,w);
      }
     Init();
     for(int i=1;i<=m;i++)
     {
         int x,y;
         scanf("%d%d",&x,&y);
         printf("%d\n",lca(x,y));
     }
  }
}

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/127140.html原文链接：https://javaforall.net

全栈程序员-站长

0 0

鸿蒙系统v30能用吗_v30pro升级鸿蒙系统使用感受

鸿蒙系统v30能用吗_v30pro升级鸿蒙系统使用感受鸿蒙鸿蒙发布在gitee上https://gitee.com/openHarmony入门指导，以Hi3516DV300为例https://gitee.com/openharmony/docs/tree/master/quick-start搭建环境在ubuntu18.4上，环境搭建可参考gitee上的入门的指导，编译顺利通过后，回头重点理一下:安装Pythonsudoaptinstall-ypythonsudoaptinstall-ypython3下载编译工具w

全栈程序员-站长
2025年12月8日
3
mysql之jdbc

mysql之jdbcJDBCjava数据库连接用来操纵mysql数据库服务器的一套api接口。大部分是接口。javajdbc各种关系数据库mysqloraclesqlserverdb2jdbc操作m

全栈程序员-站长
2022年7月1日
22
使用ComponentOne C1WebGrid控件「建议收藏」

使用ComponentOne C1WebGrid控件「建议收藏」作者：SinoryComponentOne.Studio.Enterprise.2006中的(C1StudioAspNET2_T106)是著名的C1开发的针对ASP.NET2.0的一套控件库.为ASP.NET开发人员提供了功能丰富的Web开发组件。包括个表格，报表，图表，数据，用户界面和电子商务组件等支持.C1WebGrid是其中最基本的控件之一.下面介绍它的具体应用方法:添加引用:<…

全栈程序员-站长
2022年10月6日
2
Oracle SEQUENCE 详细说明[通俗易懂]

Oracle SEQUENCE 详细说明[通俗易懂]ORACLE SEQUENCE ORACLE没有自增数据类型，如需生成业务无关的主键列或惟一约束列，可以用sequence序列实现。CREATESEQUENCE语句及参数介绍：创建序列：需要有CREATESEQUENCE或者CREATEANYSEQUENCE权限， CREATESEQUENCE[schema.]sequence [{IN

全栈程序员-站长
2022年10月18日
5
php getrealpath,php – laravel 5 – > getRealPath()doenst显示正确的值

php getrealpath,php – laravel 5 – > getRealPath()doenst显示正确的值在我的本地开发中,我使用下面显示的代码,它完美无缺,但当我将网站上传到我的共享主机时,一切正常,除了我的文件上传.我已经确定问题涉及到了–>getRealPath(),当我dd();我得到这条道路：/数据/网站/网页/christophvhbe/tmp目录如何将–>getRealPath()值更改为正确的值？$fileName=time().’-‘.$req…

全栈程序员-站长
2022年9月19日
2
javascript nextSibling属性「建议收藏」

javascript nextSibling属性「建议收藏」对于nextSibling属性，在W3school中的定义为：nextSibling属性返回指定节点之后紧跟的节点，在相同的树层级中。注意所返回的节点必须是与上一个节点是同级关系，且彼此之间不能有空格，否则将会返回：undefinedTitl</p> </div> <div class="item-meta"> <div class="item-meta-li author"> <a data-user="1" target="_blank" href="https://javaforall.net/user-2/1" class="avatar j-user-card"> <img alt='全栈程序员-站长的头像' src='https://javaforall.net/wp-content/uploads/2025/04/2025042212521933-300x300.jpg' class='avatar avatar-60 photo' height='60' width='60' /> <span>全栈程序员-站长</span> </a> </div> <span class="item-meta-li date">2022年7月13日</span> <div class="item-meta-right"> <span class="item-meta-li views" title="阅读数"><i class="wpcom-icon wi"><svg aria-hidden="true"><use xlink:href="#wi-eye"></use></svg></i>344</span> </div> </div> </div> </li> </ul> </div> <div id="comments" class="entry-comments"> <div id="respond" class="comment-respond"> <h3 id="reply-title" class="comment-reply-title">发表回复</h3><form action="https://javaforall.net/wp-comments-post.php" method="post" id="commentform" class="comment-form"><p class="comment-notes"><span id="email-notes">您的邮箱地址不会被公开。</span> <span class="required-field-message">必填项已用 <span class="required">*</span> 标注</span></p><div class="comment-form-comment"><textarea autocomplete="new-password" id="j265fd99e5" name="j265fd99e5" class="required" rows="4" placeholder="写下你的评论…"></textarea><textarea id="comment" aria-label="hp-comment" aria-hidden="true" name="comment" autocomplete="new-password" style="padding:0 !important;clip:rect(1px, 1px, 1px, 1px) !important;position:absolute !important;white-space:nowrap !important;height:1px !important;width:1px !important;overflow:hidden !important;" tabindex="-1"></textarea><script data-noptimize>document.getElementById("comment").setAttribute( "id", "ad31218a2c11405afc323dc4ba56c06c" );document.getElementById("j265fd99e5").setAttribute( "id", "comment" );</script><div class="comment-form-smile j-smilies" data-target="#comment"><i class="wpcom-icon wi smile-icon"><svg aria-hidden="true"><use xlink:href="#wi-emotion"></use></svg></i></div></div><div class="comment-form-author"><label for="author">昵称：</label><input id="author" name="author" type="text" value="" size="30"></div> <div class="comment-form-email"><label for="email">邮箱：</label><input id="email" name="email" type="text" value=""></div> <div class="comment-form-url"><label for="url">网址：</label><input id="url" name="url" type="text" value="" size="30"></div> <label class="comment-form-cookies-consent"><input id="wp-comment-cookies-consent" name="wp-comment-cookies-consent" type="checkbox" value="yes"> 记住昵称、邮箱和网址，下次评论免输入</label> <div class="form-submit"><button name="submit" type="submit" id="submit" class="wpcom-btn btn-primary btn-xs submit">提交</button> <input type='hidden' name='comment_post_ID' value='127140' id='comment_post_ID' /> <input type='hidden' name='comment_parent' id='comment_parent' value='0' /> </div></form> </div> </div> </article> </main> <aside class="sidebar"> <div class="widget widget_profile"><div class="profile-cover"><img class="j-lazy" src="https://javaforall.net/wp-content/uploads/2020/11/2020110817443450.jpg" data-original="//javaforall.net/wp-content/uploads/2025/04/anthony-delanoix-urUdKCxsTUI-unsplash-1.webp" alt="全栈程序员-站长"></div> <div class="avatar-wrap"> <a target="_blank" href="https://javaforall.net/user-2/1" class="avatar-link"><img alt='全栈程序员-站长的头像' src='https://javaforall.net/wp-content/uploads/2025/04/2025042212521933-300x300.jpg' class='avatar avatar-120 photo' height='120' width='120' /></a></div> <div class="profile-info"> <a target="_blank" href="https://javaforall.net/user-2/1" class="profile-name"><span class="author-name">全栈程序员-站长</span></a> <p class="author-description">本网站汇聚当前互联网主流语音，持续更新，欢迎关注公众号“全栈程序员社区”</p> <div class="profile-stats"> <div class="profile-stats-inner"> <div class="user-stats-item"> <b>95.5K</b> <span>文章</span> </div> <div class="user-stats-item"> <b>2</b> <span>粉丝</span> </div> </div> </div> <button type="button" class="wpcom-btn btn-xs btn-follow j-follow btn-primary" data-user="1"><i class="wpcom-icon wi"><svg aria-hidden="true"><use xlink:href="#wi-add"></use></svg></i>关注</button> </div> <div class="profile-posts"> <h3 class="widget-title"><span>最近文章</span></h3> <ul> <li><a href="https://javaforall.net/192368.html" title="缺陷报告-模板_质量缺陷报告">缺陷报告-模板_质量缺陷报告</a></li> <li><a href="https://javaforall.net/192369.html" title="Ubuntu如何安装vscode_ubuntu20.0.4 vscode配置c++环境">Ubuntu如何安装vscode_ubuntu20.0.4 vscode配置c++环境</a></li> <li><a href="https://javaforall.net/192370.html" title="C++之vector 初始化指定大小容量[通俗易懂]">C++之vector 初始化指定大小容量[通俗易懂]</a></li> <li><a href="https://javaforall.net/192371.html" title="linux命令行修改用户名_linux 更改用户密码">linux命令行修改用户名_linux 更改用户密码</a></li> <li><a href="https://javaforall.net/192372.html" title="CountDownTimer_final countdown">CountDownTimer_final countdown</a></li> <li><a href="https://javaforall.net/192373.html" title="mysql 练习题及答案 50道">mysql 练习题及答案 50道</a></li> <li><a href="https://javaforall.net/192374.html" title="京东云服务器_docker 京东自动签到">京东云服务器_docker 京东自动签到</a></li> <li><a href="https://javaforall.net/192375.html" title="U盘中毒了？教你如何删除System Volume Information这个顽固文件夹「建议收藏」">U盘中毒了？教你如何删除System Volume Information这个顽固文件夹「建议收藏」</a></li> <li><a href="https://javaforall.net/231391.html" title="Web Services 教程">Web Services 教程</a></li> <li><a href="https://javaforall.net/192376.html" title="从0到1搭建一款数据平台产品_全国大数据采集软件免费">从0到1搭建一款数据平台产品_全国大数据采集软件免费</a></li> </ul> </div> </div><div class="widget widget_post_thumb"><h3 class="widget-title"><span>最新发布</span></h3> <ul> <li class="item"> <div class="item-img"> <a class="item-img-inner" href="https://javaforall.net/192442.html" title="idea如何配置数据库连接_idea配置数据库驱动"> <img class="j-lazy" src="https://javaforall.net/wp-content/uploads/2020/11/2020110817443450-480x300.jpg" data-original="https://javaforall.net/wp-content/uploads/2020/11/2020110817443450-480x300.jpg" width="480" height="300" alt="idea如何配置数据库连接_idea配置数据库驱动"> </a> </div> <div class="item-content"> <p class="item-title"><a href="https://javaforall.net/192442.html" title="idea如何配置数据库连接_idea配置数据库驱动">idea如何配置数据库连接_idea配置数据库驱动</a></p> <p class="item-date">2025年12月15日</p> </div> </li> <li class="item"> <div class="item-img"> <a class="item-img-inner" href="https://javaforall.net/192457.html" title="idea配置Tomcat_tomcat docbase"> <img class="j-lazy" src="https://javaforall.net/wp-content/uploads/2020/11/2020110817443450-480x300.jpg" data-original="https://javaforall.net/wp-content/uploads/2020/11/2020110817443450-480x300.jpg" width="480" height="300" alt="idea配置Tomcat_tomcat docbase"> </a> </div> <div class="item-content"> <p class="item-title"><a href="https://javaforall.net/192457.html" title="idea配置Tomcat_tomcat docbase">idea配置Tomcat_tomcat docbase</a></p> <p class="item-date">2025年12月14日</p> </div> </li> <li class="item"> <div class="item-img"> <a class="item-img-inner" href="https://javaforall.net/192733.html" title="idea创建一个javaweb项目"> <img class="j-lazy" src="https://javaforall.net/wp-content/uploads/2020/11/2020110817443450-480x300.jpg" data-original="https://javaforall.net/wp-content/uploads/2020/11/2020110817443450-480x300.jpg" width="480" height="300" alt="idea创建一个javaweb项目"> </a> </div> <div class="item-content"> <p class="item-title"><a href="https://javaforall.net/192733.html" title="idea创建一个javaweb项目">idea创建一个javaweb项目</a></p> <p class="item-date">2025年12月9日</p> </div> </li> <li class="item"> <div class="item-img"> <a class="item-img-inner" href="https://javaforall.net/192761.html" title="idea社区版免费吗_intellij idea community edition"> <img class="j-lazy" src="https://javaforall.net/wp-content/uploads/2020/11/2020110817443450-480x300.jpg" data-original="https://javaforall.net/wp-content/uploads/2020/11/2020110817443450-480x300.jpg" width="480" height="300" alt="idea社区版免费吗_intellij idea community edition"> </a> </div> <div class="item-content"> <p class="item-title"><a href="https://javaforall.net/192761.html" title="idea社区版免费吗_intellij idea community edition">idea社区版免费吗_intellij idea community edition</a></p> <p class="item-date">2025年12月8日</p> </div> </li> </ul> </div> </aside> </div> </div> <footer class="footer"> <div class="container"> <div class="footer-col-wrap footer-with-logo-icon"> <div class="footer-col footer-col-logo"> <img src="http://javaforall.net/wp-content/uploads/2020/10/4545-头像.jpg" alt="全栈程序员必看"> </div> <div class="footer-col footer-col-copy"> <ul class="footer-nav hidden-xs"><li id="menu-item-152" class="menu-item menu-item-152"><a href="https://javaforall.net/contact">联系我们</a></li> </ul> <div class="copyright"> <p>Copyright ©2018-2025 版权所有 <a href="http://beian.miit.gov.cn" target="_blank" rel="nofollow noopener noreferrer">晋ICP备19011774号</a> Powered by 全栈程序员必看 <a href="/sitemap.xml" target="_blank" rel="noopener">网站地图</a></p> </div> </div> <div class="footer-col footer-col-sns"> <div class="footer-sns"> <a class="sns-wx" href="javascript:;" aria-label="icon"> <i class="wpcom-icon fa fa-wechat sns-icon"></i> <span style="background-image:url('//javaforall.net/wp-content/uploads/2020/11/2020110814274114.jpg');"></span> </a> </div> </div> </div> </div> </footer> <div class="action action-style-0 action-color-1 action-pos-0" style="bottom:15%;"> <div class="action-item"> <i class="wpcom-icon fa fa-wechat action-item-icon"></i> <div class="action-item-inner action-item-type-1"> <img class="action-item-img" src="http://javaforall.net/wp-content/uploads/2020/11/2020110814274114.jpg" alt="关注全栈程序员社区公众号"> </div> </div> <div class="action-item gotop j-top"> <i class="wpcom-icon wi action-item-icon"><svg aria-hidden="true"><use xlink:href="#wi-arrow-up-2"></use></svg></i> </div> </div> <script type="speculationrules"> {"prefetch":[{"source":"document","where":{"and":[{"href_matches":"\/*"},{"not":{"href_matches":["\/wp-*.php","\/wp-admin\/*","\/wp-content\/uploads\/*","\/wp-content\/*","\/wp-content\/plugins\/*","\/wp-content\/themes\/justnews\/*","\/*\\?(.+)"]}},{"not":{"selector_matches":"a[rel~=\"nofollow\"]"}},{"not":{"selector_matches":".no-prefetch, .no-prefetch a"}}]},"eagerness":"conservative"}]} </script> <script type="text/javascript" id="main-js-extra"> /* <![CDATA[ */ var _wpcom_js = {"webp":"","ajaxurl":"https:\/\/javaforall.net\/wp-admin\/admin-ajax.php","theme_url":"https:\/\/javaforall.net\/wp-content\/themes\/justnews","slide_speed":"5000","is_admin":"0","lang":"zh_CN","js_lang":{"share_to":"\u5206\u4eab\u5230:","copy_done":"\u590d\u5236\u6210\u529f\uff01","copy_fail":"\u6d4f\u89c8\u5668\u6682\u4e0d\u652f\u6301\u62f7\u8d1d\u529f\u80fd","confirm":"\u786e\u5b9a","qrcode":"\u4e8c\u7ef4\u7801","page_loaded":"\u5df2\u7ecf\u5230\u5e95\u4e86","no_content":"\u6682\u65e0\u5185\u5bb9","load_failed":"\u52a0\u8f7d\u5931\u8d25\uff0c\u8bf7\u7a0d\u540e\u518d\u8bd5\uff01","expand_more":"\u9605\u8bfb\u5269\u4f59 %s"},"lightbox":"1","post_id":"127140","user_card_height":"356","poster":{"notice":"\u8bf7\u300c\u70b9\u51fb\u4e0b\u8f7d\u300d\u6216\u300c\u957f\u6309\u4fdd\u5b58\u56fe\u7247\u300d\u540e\u5206\u4eab\u7ed9\u66f4\u591a\u597d\u53cb","generating":"\u6b63\u5728\u751f\u6210\u6d77\u62a5\u56fe\u7247...","failed":"\u6d77\u62a5\u56fe\u7247\u751f\u6210\u5931\u8d25"},"video_height":"482","fixed_sidebar":"1","dark_style":"0","font_url":"\/\/fonts.proxy.ustclug.org\/css2?family=Noto+Sans+SC:wght@400;500&display=swap","follow_btn":"<i class=\"wpcom-icon wi\"><svg aria-hidden=\"true\"><use xlink:href=\"#wi-add\"><\/use><\/svg><\/i>\u5173\u6ce8","followed_btn":"\u5df2\u5173\u6ce8","user_card":"1"}; /* ]]> */ </script> <script type="text/javascript" src="https://javaforall.net/wp-content/themes/justnews/js/main.js?ver=6.20.0" id="main-js"></script> <script type="text/javascript" src="https://javaforall.net/wp-content/themes/justnews/themer/assets/js/icons-2.8.9.js?ver=2.8.9" id="wpcom-icons-js"></script> <script type="text/javascript" id="wp-postviews-cache-js-extra"> /* <![CDATA[ */ var viewsCacheL10n = {"admin_ajax_url":"https:\/\/javaforall.net\/wp-admin\/admin-ajax.php","nonce":"b842d24635","post_id":"127140"}; /* ]]> */ </script> <script type="text/javascript" src="https://javaforall.net/wp-content/plugins/wp-postviews/postviews-cache.js?ver=1.77" id="wp-postviews-cache-js"></script> <script type="text/javascript" id="wpcom-member-js-extra"> /* <![CDATA[ */ var _wpmx_js = {"ajaxurl":"https:\/\/javaforall.net\/wp-admin\/admin-ajax.php","plugin_url":"https:\/\/javaforall.net\/wp-content\/plugins\/wpcom-member\/","post_id":"127140","js_lang":{"login_desc":"\u60a8\u8fd8\u672a\u767b\u5f55\uff0c\u8bf7\u767b\u5f55\u540e\u518d\u8fdb\u884c\u76f8\u5173\u64cd\u4f5c\uff01","login_title":"\u8bf7\u767b\u5f55","login_btn":"\u767b\u5f55","reg_btn":"\u6ce8\u518c"},"login_url":"https:\/\/javaforall.net\/login?modal-type=login","register_url":"https:\/\/javaforall.net\/register?modal-type=register","errors":{"require":"\u4e0d\u80fd\u4e3a\u7a7a","email":"\u8bf7\u8f93\u5165\u6b63\u786e\u7684\u7535\u5b50\u90ae\u7bb1","pls_enter":"\u8bf7\u8f93\u5165","password":"\u5bc6\u7801\u5fc5\u987b\u4e3a6~32\u4e2a\u5b57\u7b26","passcheck":"\u4e24\u6b21\u5bc6\u7801\u8f93\u5165\u4e0d\u4e00\u81f4","phone":"\u8bf7\u8f93\u5165\u6b63\u786e\u7684\u624b\u673a\u53f7\u7801","terms":"\u8bf7\u9605\u8bfb\u5e76\u540c\u610f\u6761\u6b3e","sms_code":"\u9a8c\u8bc1\u7801\u9519\u8bef","captcha_verify":"\u8bf7\u70b9\u51fb\u6309\u94ae\u8fdb\u884c\u9a8c\u8bc1","captcha_fail":"\u4eba\u673a\u9a8c\u8bc1\u5931\u8d25\uff0c\u8bf7\u91cd\u8bd5","nonce":"\u968f\u673a\u6570\u6821\u9a8c\u5931\u8d25","req_error":"\u8bf7\u6c42\u5931\u8d25"}}; /* ]]> */ </script> <script type="text/javascript" src="https://javaforall.net/wp-content/plugins/wpcom-member/js/index.js?ver=1.7.10" id="wpcom-member-js"></script> <script type="text/javascript" id="QAPress-js-js-extra"> /* <![CDATA[ */ var QAPress_js = {"ajaxurl":"https:\/\/javaforall.net\/wp-admin\/admin-ajax.php","ajaxloading":"https:\/\/javaforall.net\/wp-content\/plugins\/qapress\/images\/loading.gif","max_upload_size":"2097152","compress_img_size":"0","lang":{"delete":"\u5220\u9664","nocomment":"\u6682\u65e0\u56de\u590d","nocomment2":"\u6682\u65e0\u8bc4\u8bba","addcomment":"\u6211\u6765\u56de\u590d","submit":"\u53d1\u5e03","loading":"\u6b63\u5728\u52a0\u8f7d...","error1":"\u53c2\u6570\u9519\u8bef\uff0c\u8bf7\u91cd\u8bd5","error2":"\u8bf7\u6c42\u5931\u8d25\uff0c\u8bf7\u7a0d\u540e\u518d\u8bd5\uff01","confirm":"\u5220\u9664\u64cd\u4f5c\u65e0\u6cd5\u6062\u590d\uff0c\u5e76\u5c06\u540c\u65f6\u5220\u9664\u5f53\u524d\u56de\u590d\u7684\u8bc4\u8bba\u4fe1\u606f\uff0c\u60a8\u786e\u5b9a\u8981\u5220\u9664\u5417\uff1f","confirm2":"\u5220\u9664\u64cd\u4f5c\u65e0\u6cd5\u6062\u590d\uff0c\u60a8\u786e\u5b9a\u8981\u5220\u9664\u5417\uff1f","confirm3":"\u5220\u9664\u64cd\u4f5c\u65e0\u6cd5\u6062\u590d\uff0c\u5e76\u5c06\u540c\u65f6\u5220\u9664\u5f53\u524d\u95ee\u9898\u7684\u56de\u590d\u8bc4\u8bba\u4fe1\u606f\uff0c\u60a8\u786e\u5b9a\u8981\u5220\u9664\u5417\uff1f","deleting":"\u6b63\u5728\u5220\u9664...","success":"\u64cd\u4f5c\u6210\u529f\uff01","denied":"\u65e0\u64cd\u4f5c\u6743\u9650\uff01","error3":"\u64cd\u4f5c\u5f02\u5e38\uff0c\u8bf7\u7a0d\u540e\u518d\u8bd5\uff01","empty":"\u5185\u5bb9\u4e0d\u80fd\u4e3a\u7a7a","submitting":"\u6b63\u5728\u63d0\u4ea4...","success2":"\u63d0\u4ea4\u6210\u529f\uff01","ncomment":"0\u6761\u8bc4\u8bba","login":"\u62b1\u6b49\uff0c\u60a8\u9700\u8981\u767b\u5f55\u624d\u80fd\u8fdb\u884c\u56de\u590d","error4":"\u63d0\u4ea4\u5931\u8d25\uff0c\u8bf7\u7a0d\u540e\u518d\u8bd5\uff01","need_title":"\u8bf7\u8f93\u5165\u6807\u9898","need_cat":"\u8bf7\u9009\u62e9\u5206\u7c7b","need_content":"\u8bf7\u8f93\u5165\u5185\u5bb9","success3":"\u66f4\u65b0\u6210\u529f\uff01","success4":"\u53d1\u5e03\u6210\u529f\uff01","need_all":"\u6807\u9898\u3001\u5206\u7c7b\u548c\u5185\u5bb9\u4e0d\u80fd\u4e3a\u7a7a","length":"\u5185\u5bb9\u957f\u5ea6\u4e0d\u80fd\u5c11\u4e8e10\u4e2a\u5b57\u7b26","load_done":"\u56de\u590d\u5df2\u7ecf\u5168\u90e8\u52a0\u8f7d","load_fail":"\u52a0\u8f7d\u5931\u8d25\uff0c\u8bf7\u7a0d\u540e\u518d\u8bd5\uff01","load_more":"\u70b9\u51fb\u52a0\u8f7d\u66f4\u591a","approve":"\u786e\u5b9a\u8981\u5c06\u5f53\u524d\u95ee\u9898\u8bbe\u7f6e\u4e3a\u5ba1\u6838\u901a\u8fc7\u5417\uff1f","end":"\u5df2\u7ecf\u5230\u5e95\u4e86","upload_fail":"\u56fe\u7247\u4e0a\u4f20\u51fa\u9519\uff0c\u8bf7\u7a0d\u540e\u518d\u8bd5\uff01","file_types":"\u4ec5\u652f\u6301\u4e0a\u4f20jpg\u3001png\u3001gif\u683c\u5f0f\u7684\u56fe\u7247\u6587\u4ef6","file_size":"\u56fe\u7247\u5927\u5c0f\u4e0d\u80fd\u8d85\u8fc72M","uploading":"\u6b63\u5728\u4e0a\u4f20...","upload":"\u63d2\u5165\u56fe\u7247"}}; /* ]]> */ </script> <script type="text/javascript" src="https://javaforall.net/wp-content/plugins/qapress/js/qa.js?ver=4.10.2" id="QAPress-js-js"></script> <script type="text/javascript" src="https://javaforall.net/wp-content/themes/justnews/js/wp-embed.js?ver=6.20.0" id="wp-embed-js"></script> <script type="text/javascript" src="https://javaforall.net/wp-content/plugins/baidu-submit/assets/baidu_push.js" id="wb-baidu-push-js"></script> <script> var _hmt = _hmt || []; (function() { var hm = document.createElement("script"); hm.src = "https://hm.baidu.com/hm.js?2f4d2b9bcf94270f8bf99ccde97cb4b9"; var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(hm, s); })(); </script> <script type="application/ld+json"> { "@context": "https://schema.org", "@type": "Article", "@id": "https://javaforall.net/127140.html", "url": "https://javaforall.net/127140.html", "headline": "超级详细倍增法实现 LCA", "image": ["https://img-blog.csdn.net/20170605200944581","http://static.blog.csdn.net/xheditor/xheditor_emot/default/cry.gif","http://static.blog.csdn.net/xheditor/xheditor_emot/default/tongue.gif"], "description": "描述：倍增法用于很多算法当中，通过字面意思来理解就是翻倍增加嘛，这里着重讲使用倍增法在树中的应用求LCA；LCA是啥呢在一棵树当中 lca表示的是两个节点最近公共祖先，大家看这课树哈节点5，3的lca就是1，13和11的LCA就是6。节点8,12的lca就是8，那么我们如何通过被增来实现LCA呢。首先大家看下这个数…", "datePublished": "2022-04-09T06:20:00+08:00", "dateModified": "2022-04-09T06:20:00+08:00", "author": {"@type":"Person","name":"全栈程序员-站长","url":"https://javaforall.net/user-2/1","image":"//javaforall.net/wp-content/uploads/2025/04/2025042212371781.jpeg"} } </script> </body> </html>

超级详细 倍增法 实现 LCA

相关推荐

鸿蒙系统v30能用吗_v30pro升级鸿蒙系统使用感受

mysql之jdbc

使用ComponentOne C1WebGrid控件「建议收藏」

Oracle SEQUENCE 详细说明[通俗易懂]

php getrealpath,php – laravel 5 – > getRealPath()doenst显示正确的值

javascript nextSibling属性「建议收藏」

超级详细倍增法实现 LCA