最近公共祖先（lca）与树上叉分

我不是女神ヾ 2021-11-29 23:58 270阅读 0赞

lca的定义不在过多解释，

代码如下：

inline void bfs()
    {
        queue<int>q;
        deep[s]=1;q.push(s);
        while(!q.empty())
        {
            int x=q.front();q.pop();
            for(int i=link[x],y;i;i=a[i].next)
            {
                if(deep[y=a[i].y]) continue; //如果搜索到的节点，深度已经
                deep[y]=deep[x]+1; //有值，则说明已经便利过了.
                f[y][0]=x;q.push(y);
                for(int j=1;j<=20;++j) f[y][j]=f[f[y][j-1]][j-1];
            }
        }
    }
    inline void lca(int x,int y)
    {
        if(deep[x]>deep[y]) swap(s,y); //将深度大的放在y上. 
        for(int i=20;i>=0;--i)
            if(deep[f[y][i]]>=deep[x]) y=f[y][i]; //将y一直跳到和x深度一样 
        if(x==y) return x;
        for(int i=20;i>=0;--i)
            if(f[y][i]!=f[x][i])
                x=f[x][i],y=f[y][i];   //将x与y同时跳到lca的两个儿子. 
        return f[x][0];              
    }

树上叉分：用于树上两点以及之间的路径上各个点点区间修改：

例如：（x，y）之间路径上的点都加一，可以将x++，y++，lca（x，y）--,fa\[lca(x,y)\]--;最后统计各个点的权值即可.

转载于:https://www.cnblogs.com/gcfer/p/11125781.html

发表评论取消回复

表情：

评论列表（有 0 条评论，270人围观）

还没有评论，来说两句吧...

相关阅读

相关求二叉树最近公共祖先LCA的brute-force算法

概念先来一张绝妙的百科配图 ![先来一张绝妙的百科配图][70] 最近公共祖先(Lowest/Least Common Ancestor, LCA) > 在图

亦凉/ 2023年10月17日 23:55/ 0 赞/ 120 阅读

相关最近公共祖先LCA

最近公共祖先（Lowest Common Ancestors，LCA）指有根树中距离两个节点最近的公共祖先。祖先指从当前节点到树根路径上的所有节点。 ![2021042810

蔚落/ 2023年01月17日 08:29/ 0 赞/ 145 阅读

相关 leetcode---236. 二叉树的最近公共祖先(最近公共祖先)

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是

矫情吗；*/ 2022年11月28日 00:42/ 0 赞/ 205 阅读

相关 leetcode---235. 二叉搜索树的最近公共祖先（最近公共祖先）

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x

女爷i/ 2022年11月28日 00:42/ 0 赞/ 202 阅读

相关二叉树最近公共祖先问题

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是

喜欢ヅ旅行/ 2022年10月05日 04:41/ 0 赞/ 192 阅读

相关求二叉搜索树的最近公共祖先(与那个普通二叉树最近公共祖先类似)

文章目录求二叉搜索树的最近公共祖先题目描述题目链接解题思路求二叉搜索树的最近公共祖先

谁借莪１个温暖的怀抱￠/ 2022年09月05日 12:58/ 0 赞/ 184 阅读

相关 LCA 最近公共祖先

[https://www.cnblogs.com/JVxie/p/4854719.html][https_www.cnblogs.com_JVxie_p_4854719.htm

Myth丶恋晨/ 2022年06月02日 11:37/ 0 赞/ 181 阅读

相关【leetcode】二叉树最近公共祖先

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

╰半夏微凉°/ 2022年03月14日 14:50/ 0 赞/ 233 阅读

相关 LCA最近公共祖先-- HDU 2586

[题目链接][Link 1] Problem Description There are n houses in the village and some bidir

「爱情、让人受尽委屈。」/ 2021年12月01日 17:34/ 0 赞/ 264 阅读

相关最近公共祖先（lca）与树上叉分

lca的定义不在过多解释，代码如下： inline void bfs() { queue<int>q; deep[s]=1

我不是女神ヾ/ 2021年11月29日 23:58/ 0 赞/ 271 阅读