精华内容
下载资源
问答
  • 每日一算,公共祖先问题  分类 单根,那么 直接 dfs(root) #include<bits/stdc++.h> using namespace std; #define LOACL freopen("in","r",stdin);\ freopen("out","w",stdout); #define FOR(i, a...

    每日一算,公共祖先问题

      分类 单根,那么 直接 dfs(root)

    #include<bits/stdc++.h>
    using namespace std;
    #define LOACL  freopen("in","r",stdin);\
             freopen("out","w",stdout); 
    #define FOR(i, a, b)  for(int i=(a); i<(b); i++)
    #define REP(i, a, b)  for(int i=(a); i<=(b); i++)
    #define DOWN(i, a, b) for(int i=(a); i>=(b); i--)
    #define sz 1000100
    #define demen 21
    
    int n,m,s,tot,u,v,head[sz],fa[sz][demen],d[sz];
    struct node
    {int t,nxt;}e[sz];
    void add(int u,int v)
    { e[++tot]=(node){v,head[u]},head[u]=tot;}
    
    void dfs(int rt,int f)
    {
        d[rt] =d[f]+1;
        fa[rt][0] = f;
        REP(i,1,20)
            fa[rt][i] =fa[fa[rt][i-1]][i-1];
        for(int i=head[rt];i;i=e[i].nxt)
             if(e[i].t!=f)
                dfs(e[i].t,rt);
    }
    int lca(int x,int y)
    {
        if(d[x]<d[y])swap(x,y);
    
        int dre = d[x] - d[y];
        DOWN(i,20,0)
            if((1<<i)&dre)
                x = fa[x][i];
        if(x==y)return x;
        DOWN(i,20,0)
        if(fa[x][i]!=fa[y][i])
            x = fa[x][i],y=fa[y][i];
        return fa[x][0];
    }
    
    
    int main()
    {
        //LOACL
         ios::sync_with_stdio(false);
     
        cin>>n>>m>>s;    
        REP(i,1,n-1)
        {
            cin>>u>>v;
              
              add(u,v),add(v,u);           
        }
        dfs(s,0);
        REP(i,1,m)
        { 
            cin>>u>>v;
            
              printf("%d\n",lca(u,v));
        } 
        return 0;
    }
    View Code

      多个根 那么就记搜

    #include<bits/stdc++.h>
    using namespace std;
    #define LOACL  freopen("in","r",stdin);\
             freopen("out","w",stdout); 
    #define FASTIO  ios::sync_with_stdio(false);
    #define CLR(arr,val) memset(arr,val,sizeof(arr)) 
    #define DBG(x) cout<<(#x)<<"="<<x<<endl
    #define DBG2(x,y) cout<<(#x)<<"="<<x<<"\t"<<(#y)<<"="<<y<<endl
    #define DBG3(x,y,z) cout<<(#x)<<"="<<x<<"\t"<<(#y)<<"="<<y<<"\t"<<(#z)<<"="<<z<<endl
     
    #define FOR(i, a, b)  for(int i=(a); i<(b); i++)
    #define REP(i, a, b)  for(int i=(a); i<=(b); i++)
    #define DOWN(i, a, b) for(int i=(a); i>=(b); i--)
    
    #define INF 999999999
    const int sz = 30000*2;
    int n,m,x,y,z,tot,q;
    int head[sz],deep[sz],fa[sz],f[sz][21],w[sz][21];
    bool vis[sz];
    struct node
    {
        int u,v,w; 
    }a[sz];
    struct edge
    {
        int v,nxt,w;
    }e[sz<<1];
    bool cmp(node l ,node r)
    {
        return l.w>r.w;
    }
    int getf(int x)
    {
        if(x!=fa[x])fa[x]=getf(fa[x]);
        return fa[x];
    }
    void add(int u ,int v,int w )
    {
          e[++tot] =(edge){v,head[u],w},head[u]=tot;
        e[++tot] =(edge){u,head[v],w},head[v]=tot;
    }
    
    void krusual()
    {
        sort(a+1,a+m+1,cmp);
        REP(i,1,n) fa[i]=i; 
        REP(i,1,m)
        {
            if(getf(a[i].u)!=getf(a[i].v))
            {
                fa[getf(a[i].u)] = getf(a[i].v);
                add(a[i].u,a[i].v,a[i].w);
            }    
        }
    }
     
    void dfs(int x)
    {
        vis[x] = true;
        for(int i = head[x];i;i=e[i].nxt)
        {
            int v = e[i].v;
            if(vis[v]) continue;
            deep[v] =deep[x]+1;
            f[v][0] = x;
            w[v][0] = e[i].w;
            dfs(v); 
        }
    }
    int lca (int x,int y)
    {  
     
        if(getf(x)!=getf(y)) return -1;
        int ans=INF;
        if(deep[x]<deep[y])swap(x,y);
    
        DOWN(i,20,0)
            if(deep[f[x][i]]>=deep[y])
            {
                
                ans=min(ans,w[x][i]);
                x = f[x][i];
            }    
    
    
        if(x==y) return ans;
     
        DOWN(i,20,0)
        {
            if(f[x][i]!=f[y][i])
            {
                ans=min(ans,min(w[x][i],w[y][i]));
                x=f[x][i],y=f[y][i];
            }
        }    
         ans = min(ans,min(w[x][0],w[y][0]));
        return ans;
    
    }
    
    int lca1(int x,int y)
    {
        if(getf(x)!=getf(y)) return -1;
        int ans=INF;
        if(deep[x]>deep[y]) swap(x,y);
        DOWN(i,20,0)
        {
            if(deep[f[y][i]] >=deep[x])
            {
                ans = min(ans,w[y][i]);
                y=f[y][i];
            }
        }
        if(x==y) return ans; 
        DOWN(i,20,0)
        {
            if(f[x][i]!=f[y][i])
            {
                ans=min(ans,min(w[x][i],w[y][i]));
                x=f[x][i],y=f[y][i];
            }
        }
        ans = min(ans,min(w[x][0],w[y][0]));
        return ans;
    }
    
    
    int main()
    {
        LOACL
        FASTIO
        cin>>n>>m;
        REP(i,1,m)
            cin>>a[i].u>>a[i].v>>a[i].w;
         krusual();
    
         //先 dfs 一下 然后 init lca 
         REP(i,1,n)
         {
             if(!vis[i])
             {
                 deep[i]=1;
                 dfs(i);
                 f[i][0]=i;
                 w[i][0]=INF;
             }
         }
    
     //   REP(i,1,n) DBG3(i,f[i][0],w[i][0]);
    
         REP(j,1,20) REP(i,1,n)
         {
             f[i][j] =f[f[i][j-1]][j-1];
             w[i][j] =min(w[i][j-1],w[f[i][j-1]][j-1]);    
         }
         //REP(i,1,n) DBG3( w[i][0],f[i][0], deep[i]);
         cin>>q;
         REP(i,1,q)
         {
             cin>>x>>y;
             cout<<lca(x,y)<<endl;
         } 
    
        return 0;
    }
    View Code

      涉及到一个lca(x,y) 这个函数 的注意事项:

      需要的 核心跳转 倍增思想,什么意思呢,记得做填那个神奇算法,硬币分包问题吗?

      2^i 会产生对2^(i+1) 影响跳转 ,是不是很神奇,一下子就 砍到了 lg(n) 完全符合算法的思维,n===>lgn 的进化.

      

    转载于:https://www.cnblogs.com/corx/p/8824245.html

    展开全文
  • LCA是在一棵树上求两个点的最近公共祖先。两个点共同能到达的点,这样的点我们称它为公共祖先,那么两个点共同能到达的第一个点,这样的点我们称它为最近公共祖先 算法内容 前置技能 您需要去了解 邻接表存图 倍增...

    学习LCA前提须知

    LCA是在一棵树上求两个点的最近公共祖先。两个点共同能到达的点,这样的点我们称它为公共祖先,那么两个点共同能到达的第一个点,这样的点我们称它为最近公共祖先

    算法内容

    前置技能

    您需要去了解 邻接表存图 倍增算法基本原理 高中必修一log函数计算

    竞赛需要用到的点

    1、LCA常作为思维题的工具,不单独考

    2、倍增LCA必加优化,或者可以选择常数更优秀的树剖求LCA

    倍增求LCA略讲

    考虑常规算法求LCA,我们需要知道当前查找的两个点是否遍历过了同一个点上,若一旦有被两点都遍历到的点,那么当前点就是我们的最近公共祖先。我们现在的问题就是,如何找到这样的点?考虑从路径入手,我们一开始的朴素算法能够想到的就是一个一个往上走,但实际上走的很多点都不会用到,我们考虑一个二分的逆运算,倍增

    我们从倍增入手,倍增的基本原理就是,从某一个点(数)出发,进行二的次幂级别的运动,并且判断当前是否满足条件,若不满足再次进行跳跃,每一次跳跃都是上一次跳跃路径长度的 2 倍。那就这样跳?肯定是不行的,因为你不知道何时停止,如果不加限制条件,那么就可能判断整棵树的根节点为它们的最近公共祖先,这肯定是错误的,那如何加限制条件呢?

    我们现在的目标很明确,就是用倍增向上跳找到最近公共祖先,那我们应该怎样加限制条件呢?我们可以很轻松得到,当它们在同一深度时,若它们的节点不同,那么肯定是还没到达任何一个公共祖先,那么当我们满足 当前两点同深度,不同点并且不能够再往上跳 的时候,是不是意味着再往上走一个点就是我们的最终答案了呢?答案是肯定的。

    那我们就可以开始写代码了

    部分代码展现

    首先是设变量和邻接表

    //#define fre yes
    
    #include <cstdio>
    #include <cstring> // memset
    
    const int N = 100005;
    int head[N << 1], to[N << 1], ver[N << 1];
    int depth[N], f[N][22], lg[N];
    // depth代表深度 设f[x][k]的话就是 x点向上走2^k步
    // lg就是我们的优化
    
    int tot;
    void addedge(int x, int y) {
        ver[tot] = y;
        to[tot] = head[x];
        head[x] = tot++;
    }
    
    int main() {
        memset(head, -1, sizeof(head));
        ...
    }

    然后我们需要来一个先将我们的depth数组和f数组起始化的函数,并且加上我们的优化

    void dfs(int x, int fa) { //x为当前节点 fa为x的上一个节点
        depth[x] = depth[fa] + 1;
        f[x][0] = fa;
        for (int i = 1; (1 << i) <= depth[x]; i++) {
            f[x][i] = f[f[x][i - 1]][i - 1];
            //这里是一个推导公式
            //x向上走2^i 相当于x向上走2^{i - 1} + 2^{i - 1}
        }
        
        for (int i = head[x]; ~i; i = to[i]) {
            int v = ver[i];
            if(v != fa) {
                dfs(v, x);
            }
        }
    }
    
    int main() {
        static int n; //n个点
        ...
        for (int i = 1; i <= n; i++) {
            lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
        }
        dfs(root, -1);
        ...
    }

    起始化了之后就可以求我们的LCA了

    #include <iostream>
    int lca(int x, int y) {
        if(depth[x] < depth[y]) {
            std::swap(x, y);
        }
        
        while(depth[x] > depth[y]) {
            x = f[x][lg[depth[x] - depth[y]] - 1];
            //这样就能让x能跑到y的深度
        }
        
        if(x == y) return x; //如果直接相等了 那么x肯定是的最近公共祖先
        
        for (int k = lg[depth[x]] - 1; i >= 0; i--) {
            //这里也是一句优化 即跑到顶最少需要多少次2^k
            if(fa[x][k] != fa[y][k]) {
                //如果不相等 那么满足条件 向上跳
                x = fa[x][k];
                y = fa[y][k];
            }
        } return fa[x][0];
    }

    完整代码

    //#define fre yes
    
    #include <cstdio>
    #include <cstring>
    #include <iostream>
    
    const int N = 500005;
    int head[N << 1], ver[N << 1], to[N << 1];
    int lg[N], depth[N], f[N][22];
    
    int tot;
    void addedge(int x, int y) {
        ver[tot] = y;
        to[tot] = head[x];
        head[x] = tot++;
    }
    
    void dfs(int x, int fa) {
        depth[x] = depth[fa] + 1;
        f[x][0] = fa;
        for (int i = 1; (1 << i) <= depth[x]; i++) {
            f[x][i] = f[f[x][i - 1]][i - 1];
        }
        
        for (int i = head[x]; ~i; i = to[i]) {
            int v = ver[i];
            if(v != fa) {
                dfs(v, x);
            }
        }
    }
    
    int lca(int x, int y) {
        if(depth[x] < depth[y]) {
            std::swap(x, y);
        }
        
        while(depth[x] > depth[y]) {
            x = f[x][lg[depth[x] - depth[y]] - 1];
        }
        
        if(x == y) return x;
        
        for (int k = lg[depth[x]] - 1; k >= 0; k--) {
            if(f[x][k] != f[y][k]) {
                x = f[x][k]; y = f[y][k];
            } 
        } return f[x][0];
    }
    
    int main() {
        memset(head, -1, sizeof(head));
        static int n, m, s;
        scanf("%d %d %d", &n, &m, &s);
        for (int i = 1; i < n; i++) {
            int x, y;
            scanf("%d %d", &x, &y);
            addedge(x, y);
            addedge(y, x);
        }
        
        for (int i = 1; i <= n; i++) {
            lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
        } dfs(s, 0);
        
        for (int i = 1; i <= m; i++) {
            int x, y;
            scanf("%d %d", &x, &y);
            printf("%d\n", lca(x, y));
        } return 0;
    }

    转载于:https://www.cnblogs.com/Nicoppa/p/11471149.html

    展开全文
  • 求LCA——最近公共祖先 倍增算法

    千次阅读 2018-08-07 21:36:10
    LCA是啥呢,LCA就是一棵树里两个节点的最近公共祖先,如下图 2号节点和3号节点的LCA就是1, 5号节点和11号节点的LCA就是2,8号节点和4号节点的lca就是4 那么怎么求LCA呢。首先要建树,然后最容易想到的就是两个...

    LCA是啥呢,LCA就是一棵树里两个节点的最近公共祖先,如下图

    2号节点和3号节点的LCA就是1, 5号节点和11号节点的LCA就是2,8号节点和4号节点的lca就是4

    那么怎么求LCA呢。首先要建树,然后最容易想到的就是两个节点一起向上跳,第一个相遇的节点就是LCA

    输入输出格式可参考洛谷P3379 LCA模板题

    输入格式:

    第一行包含三个正整数N、M、S,分别表示树的结点个数、询问的个数和树根结点的序号。

    接下来N-1行每行包含两个正整数x、y,表示x结点和y结点之间有一条直接连接的边(数据保证可以构成树)。

    接下来M行每行包含两个正整数a、b,表示询问a结点和b结点的最近公共祖先。

    输出格式:

    输出包含M行,每行包含一个正整数,依次为每一个询问的结果。

     

    先用邻接表存路径。

    void add(int x,int y)
    {
        to[++cnt]=y;
        nxt[cnt]=head[x];
        head[x]=cnt;
    }
    
    int main()
    {
        n=read();m=read();s=read();
        int i,x,y;
        for(i=1;i<n;i++)
        {
            x=read();y=read();
            add(x,y);
            add(y,x);
        }
        return 0;
    }

    存路径后,我们用dfs建树,把每个节点的深度记录下来

    void dfs(int x,int fa)//fa表示父节点编号
    {
        int i;
        f[x]=fa;//f[x]表示x节点的父节点
        d[x]=d[fa]+1;
        for(i=head[x];i;i=nxt[i])
            if(to[i]!=fa)
                dfs(to[i],x);
    }

    其次需要先把两个节点跳到同一深度,然后一起往上跳即可

    int work(int x,int y)
    {
        int i;
        if(d[x]<d[y])
            swap(x,y);
        while(d[x]>d[y])
        	x=f[x];//移动至同一深度
        while(x!=y)
        	x=f[x],y=f[y];
        return x;
    }

    以上就是暴力求LCA,以为能AC吗??妥妥的TLE!!!

    那么为什么T呢?是因为一次只移动到父亲节点要跳好多次,这样太慢了!

    那么怎么才能快点呢?就要用倍增了!设一个grd[x][i]数组表示x节点想上跳2的i次方后的节点。所以i<=log2(n)

    这个数组怎么用呢?令d[x]>=d[y]。首先还是要跳到同一深度中,先让x跳2^20次(最大)。假设我们发现深度比y小了,这就表示跳过了,我们再试试跳2^19次,如果还过了,那就再变小。如果发现深度还没到,那就跳呗,接着我们再跳,就该试试跳2^18次了,为什么不能跳两个2^19次呢?这是以为两个2^19次就是2^20次啊,肯定可以不用跳两次相同的。这样跳就能大大减少时间了。

    到同一深度后,就是两个点一起往上跳了。我们还是让两个点跳2^20次,如果发现跳完后相同了,就可以确定跳到祖先了,但不一定是最近的,所以我们先不着急跳,接着,试试跳2^19次,如果还是相同,那就再变小,如果不相同,那就跳(跟上面差不多),最后跳完,可以确定x和y再向上跳一次就是LCA了,因为我们跳的时候判定了如果跳之后相同那就不跳。但是注意,当y是x的祖先时,跳到同一深度时x==y已经是LCA了,此时就不用再往上跳了。

    举个栗子,还是刚才那张图,我们模拟一下求11和7的LCA                                                                                                               

    首先移动到同一深度,d[7]=3,d[11]=4,所以我们从2^20次(最大)开始,一直到2^1都不行,所以节点11跳了2^0次跳到了节点6。

    接着两个节点一块儿跳,从2^20次,最后还是只能跳2^0次,变成了节点2和节点3,最终再跳一次即节点1就是LCA。

    em……这个栗子有点小。。。。。。。

    好了,那怎么预处理grd数组呢?我们可以在dfs建树的时候预处理,那么我们可以确定grd[x][0]就是他的爸爸,那么怎么确定grd[x][1]呢?grd[x][1]不就是爸爸的爸爸(爷爷)嘛,所以grd[x][1]=grd [ grd [ x ] [ 0 ] ] [ 0 ](为了让大家看清楚特意用空格隔开嘿嘿嘿),那么grd[x][2]呢(注意这是爷爷的爷爷,而不是爷爷的爸爸)?爷爷的爷爷不就等于grd [ grd [ x ] [ 1 ] ] [ 1 ]嘛。

    以此类推,我们得出grd[x][i]=grd[ grd [ x ] [ i - 1 ] ] [ i - 1 ]。是因为2^(i-1)+2(i-1)=2^i,即往上跳两次2^(i-1)就是往上跳2^i

    好了我们再捋一遍思路,邻接表+预处理grd数组+跳到相同深度+一起往上跳,代码如下。

    #include <iostream>
    #include <cstdio>
    #include <cctype>
    #include <cstring>
    
    using namespace std;
    
    inline int read()
    {
        int f=1,x=0;
        char c=getchar();
        while(!isdigit(c)){if(c=='-')f*=-1;c=getchar();}
        while(isdigit(c)){x=x*10+c-'0';c=getchar();}
        return x*f;
    }
    
    const int N=5e5+5;
    int a[N],n,m,s,to[N<<1],head[N],nxt[N<<1],grd[N][23],d[N],cnt;
    
    void add(int x,int y)
    {
        to[++cnt]=y;
        nxt[cnt]=head[x];
        head[x]=cnt;//邻接表
    }
    
    void dfs(int x,int fa)
    {
        int i;
        grd[x][0]=fa;//父节点
        d[x]=d[fa]+1;
        for(i=1;i<21;i++)//其实到本题19就可以了,习惯到20整一点哈哈哈
            grd[x][i]=grd[grd[x][i-1]][i-1];//预处理grd数组
        for(i=head[x];i;i=nxt[i])
            if(to[i]!=fa)
                dfs(to[i],x);
    }
    
    int lca(int x,int y)
    {
        int i;
        if(d[x]<d[y])
            swap(x,y);
        for(i=20;i>=0;i--)//从大到小枚举
            if((1<<i)<=d[x]-d[y])//1<<i就是2^i,也可以预处理成数组
                x=grd[x][i];
        if(x==y)
            return x;//当y是x的祖先时
        for(i=20;i>=0;i--)
            if(grd[x][i]!=grd[y][i])
                x=grd[x][i],y=grd[y][i];//一起往上跳
        return grd[x][0];//返回父节点
    }
    
    int main()
    {
        n=read();m=read();s=read();
        int i,j,x,y;
        for(i=1;i<n;i++)
        {
            x=read();y=read();
            add(x,y);
            add(y,x);//邻接表
        }
        dfs(s,0);//预处理
        for(i=1;i<=m;i++)
        {
            x=read();y=read();
            printf("%d\n",lca(x,y));
        }
        return 0;
    }

    当然,遇到相应的题可再加数组,比如有时可定义dis[x][i]表示x节点向上跳2^i的距离(权),或者表示最大最小值等。

    展开全文
  • 这道题很明显的LCA了 一般求LCA方法 先建树,求U,VU,VU,V的...在1的基础上改进,引入了一个预处理好的表来记录往上跳20,21,22...2k2^0,2^1,2^2...2^k20,21,22...2k步的祖先 需要先dfsdfsdfs把这个表预处理出来

    这道题很明显的LCA了

    1. 一般求LCA方法
    • 先建树,求U,VU,VLCALCA
    • 如果UVU和V深度不相同,先把深的那个点向上爬到同一层
    • 如果已经跳到相同层了,就U,VU,V一起向上跳,直到U==VU==V


    2. 倍增求LCA O(nlogn)O(nlogn)

    • 在1的基础上改进,引入了一个预处理好的表来记录往上跳20,21,22...2k2^0,2^1,2^2...2^k步的祖先
    • 需要先dfsdfs把这个表预处理出来(可以在建树的时候就预处理出跳表)
    void dfs_build(vector<string>& mtx, int u, int father) {
    	vis[u] = true;
    	level[u] = level[father]+1;          //更新当前递归到的点的深度
    	up[u][0] = father;                   //向上跳2^0=1,就是跳到爹上
    
    	for(int i=1; (1<<i)<=level[u]; i++)  //2^j = (2^j-1) + 2^(j-1)
    		up[u][i] = up[up[u][i-1]][i-1];
    
    	for(int i=0; i<n; i++) {
    		int v = i;
    		if(v == u || vis[v] || mtx[u][v] == '0') continue ;
    		fa[v] = u;                      //建立父子关系
    		dfs_build(mtx, v, u);
    	}
    }    
    

    求LCA

    int lca(int u, int v) {
    	if(level[u] > level[v]) swap(u, v);
    	for(int i=L; i>=0; i--)
    		if(level[u] <= level[v]-(1<<i)) 
    			v = up[v][i];
    	if(u == v) return u;
    	for(int i=L; i>=0; i--)
    		if(up[u][i] == up[v][i]) continue ;
    		else {
    			u = up[u][i];
    			v = up[v][i];
    		}
    	return up[u][0];
    }
    


    3. Tarjan求LCA (离线算法)

    • 不会

    本题代码

    #define debug
    #ifdef debug
    #include <time.h>
    #include "/home/majiao/mb.h"
    #endif
    
    #include <iostream>
    #include <algorithm>
    #include <vector>
    #include <string.h>
    #include <map>
    #include <set>
    #include <stack>
    #include <queue>
    #include <math.h>
    
    #define MAXN (2048)
    #define ll long long 
    #define INF (0x7f7f7f7f)
    #define fori(lef, rig) for(int i=lef; i<=rig; i++)
    #define forj(lef, rig) for(int j=lef; j<=rig; j++)
    #define fork(lef, rig) for(int k=lef; k<=rig; k++)
    #define QAQ (0)
    
    using namespace std;
    
    #define show(x...) \
    	do { \
    		cout << "\033[31;1m " << #x << " -> "; \
    		err(x); \
    	} while (0)
    
    void err() { cout << "\033[39;0m" << endl; }
    template<typename T, typename... A>
    void err(T a, A... x) { cout << a << ' '; err(x...); }
    
    namespace FastIO {
    
    	char print_f[105];
    	void read() { }
    	void print() { putchar('\n'); }
    
    	template <typename T, typename... T2>
    		inline void read(T &x, T2 &... oth) {
    			x = 0;
    			char ch = getchar();
    			ll f = 1;
    			while (!isdigit(ch)) {
    				if (ch == '-') f *= -1; 
    				ch = getchar();
    			}
    			while (isdigit(ch)) {
    				x = x * 10 + ch - 48;
    				ch = getchar();
    			}
    			x *= f;
    			read(oth...);
    		}
    	template <typename T, typename... T2>
    		inline void print(T x, T2... oth) {
    			ll p3=-1;
    			if(x<0) putchar('-'), x=-x;
    			do{
    				print_f[++p3] = x%10 + 48;
    			} while(x/=10);
    			while(p3>=0) putchar(print_f[p3--]);
    			putchar(' ');
    			print(oth...);
    		}
    } // namespace FastIO
    using FastIO::print;
    using FastIO::read;
    
    int n, m, Q, K;
    #if 0 //非倍增的普通求LCA
    bool vis[MAXN];
    int level[MAXN], fa[MAXN];                  //fa[i]表示i的父节点
    
    #define cls(x) (memset(x, false, sizeof(x)))
    
    class Solution {
    public:
    	int n;
    
    	void init(vector<string>& mtx) {
    		n = mtx.size();
    		cls(level), cls(fa), cls(vis);
    	}
    
    	void dfs_build(vector<string>& mtx, int u, int dep) {
    		vis[u] = true;
    		level[u] = dep;                     //更新当前递归到的点的深度
    		for(int i=0; i<n; i++) {
    			int v = i;
    			if(v == u || vis[v] || mtx[u][v] == '0') continue ;
    			fa[v] = u;                      //建立父子关系
    			dfs_build(mtx, v, dep+1);
    		}
    	}
    
        int getSplitNode(vector<string>& mtx, int u, int v) {
    		init(mtx);
    		dfs_build(mtx, 0, 0);               //先dfs建树
    
    		int lu = level[u], lv = level[v];
    
    		while(lu < lv)                      //把u和v爬到同一层
    		   	lv = level[fa[v]], v = fa[v];
    		while(lv < lu) 
    			lu = level[fa[u]], u = fa[u];
    
    		while(u != v)                       //u和v一起向上爬
    			u = fa[u], v = fa[v];
    		return u;
        }
    };
    
    #else  //倍增求LCA
    
    #define L (20)
    bool vis[MAXN];
    int level[MAXN], fa[MAXN];                  //fa[i]表示i的父节点
    int up[MAXN][L+5];                            //跳表
    
    #define cls(x) (memset(x, false, sizeof(x)))
    
    class Solution {
    public:
    	int n;
    
    	void init(vector<string>& mtx) {
    		n = mtx.size();
    		cls(level), cls(fa), cls(vis), cls(up);
    	}
    
    	void dfs_build(vector<string>& mtx, int u, int father) {
    		vis[u] = true;
    		level[u] = level[father]+1;          //更新当前递归到的点的深度
    		up[u][0] = father;                   //向上跳2^0=1,就是跳到爹上
    
    		for(int i=1; (1<<i)<=level[u]; i++)  //2^j = (2^j-1) + 2^(j-1)
    			up[u][i] = up[up[u][i-1]][i-1];
    
    		for(int i=0; i<n; i++) {
    			int v = i;
    			if(v == u || vis[v] || mtx[u][v] == '0') continue ;
    			fa[v] = u;                      //建立父子关系
    			dfs_build(mtx, v, u);
    		}
    	}
    
    	int lca(int u, int v) {
    		if(level[u] > level[v]) swap(u, v);
    		for(int i=L; i>=0; i--)
    			if(level[u] <= level[v]-(1<<i)) 
    				v = up[v][i];
    		if(u == v) return u;
    		for(int i=L; i>=0; i--)
    			if(up[u][i] == up[v][i]) continue ;
    			else {
    				u = up[u][i];
    				v = up[v][i];
    			}
    		return up[u][0];
    	}
    
        int getSplitNode(vector<string>& mtx, int u, int v) {
    		init(mtx);
    #if 0
    		fori(0, n-1)
    			forj(0, n-1)
    				if(mtx[i][j] == '1') printf("%d %d\n", i, j);
    #endif
    		dfs_build(mtx, 0, 0);               //先dfs建树
    #if 0
    		forarr(level, 0, n-1, "level");
    		forarr(fa, 0, n-1, "fa   ");
    #endif
    		return lca(u, v);
        }
    };
    
    #endif
    
    
    #if 1
    int main() {
    #ifdef debug
    	freopen("test", "r", stdin);
    	// freopen("out_main", "w", stdout);
    	clock_t stime = clock();
    #endif
    
    	vector<string> mtx = {
    		"0110000000","1000101000","1001000000","0010000000","0100000101",
    		"0000001000","0100010010","0000100000","0000001000","0000100000"
    	};
    	Solution s;
    	int U = 6, V = 7;
    	cout << s.getSplitNode(mtx, U, V);
    
    
    #ifdef debug
    	clock_t etime = clock();
    	printf("rum time: %lf 秒\n",(double) (etime-stime)/CLOCKS_PER_SEC);
    #endif 
    	return 0;
    }
    
    
    #endif
    
    
    展开全文
  • 解题思路:这是一道比较标准的最近公共祖先的模板题,所以就根据这道题总结一下这类算法,做这道题采用的方法是倍增法,思路如下 1.建图完成后,我们根据从其中任意点开始标记层次,最近公共祖先的原理就是根据...
  • 最近公共祖先 LCA 倍增算法倍增算法可以在线求树上两个点的LCA,时间复杂度为nlogn预处理:通过dfs遍历,记录每个节点到根节点的距离dist[u],深度d[u]init()求出树上每个节点u的2^i祖先p[u][i]求最近公共祖先,根据...
  • LCA 最近公共祖先倍增算法) 首先了解一下我们 最近公共祖先 E和G的LCA为A L和J的LCA为D K和F的LCA为B 然后 倍增 用到了二进制和 dp 的思想 倍增 就是 1 2 4 8 16 …任何一个数 都是可以右 这些数相加得到的。...
  • 模板题是这个样子的:给你一颗有根树,每次查询两个节点的最近公共祖先。 &amp;nbsp; &amp;nbsp; &amp;nbsp; &amp;nbsp;最近公共祖先为何物?简单来说,就是两点间的路径中深度最小的那个节点。 &...
  • 描述:倍增法用于很多算法当中,通过字面意思来理解就是翻倍增加嘛,...LCA是啥呢 在一棵树当中 lca表示的是两个节点最近公共祖先, 大家看这课树哈节点5 ,3的lca就是1,13和11的LCA就是6。节点8,12的lca就是8...
  • lac即最近公共祖先,u和v最近公共祖先就是两节点公用的祖先中深度最大的 比如 其中 lca(1,2)=4, lca(2,3)=4, lca(3,5)=1, lca(2,5)=4; 如何求LCA? 树上倍增版: 预处理每一个节点的深度depth[i]; 选定两节点; 将...
  • 通常在OI中最近公共祖先的解决办法分为在线做法和离线做法,离线做法也就是Tarjan算法,而在线做法则是倍增做法。========================================= Tarjan做法:利用并查集优越的时空复杂度,我们可以...
  • 最近公共祖先有多种算法 如倍增,RMQ,树链剖分等这里先介绍倍增算法 预处理复杂度nlog(n); 询问复杂度log(n);倍增与二进制息息相关 与分块的算法有些相似之处使用倍增算法时开一个fa[n][S]数组 fa[i][j] 表示 ...
  • 最近公共祖先, 树上倍增,LCA, fa [ i ] [ j ] 表示 i 节点向上 2j 的祖先 很像dp, k 属于 [ 1 , log ( n ) ] ,f [ x ][ k ] = f [ f [ x ] [ k-1 ]] [k-1] 算lca时, 先不妨设 d [ x ] >= d [ y ] 二进制...
  • 注意是最近公共祖先。 #include #include #include #include #include using namespace std; const int maxN=20+2; int anc[1005][25]; vector <int > tree[1005]; int deep[1005],n; void dfs...
  • --i){//跳到最近公共祖先的下一层 if(father[u][i] != father[v][i]){ u = father[u][i]; v = father[v][i]; } } return father[u][0]; } int main(){ scanf("%d%d%d", &n, &m, &s); int x, y; for...
  • 【简介】 解决LCA问题的倍增法是一种基于倍增思想的在线算法。... 对于每个节点u , ancestors[u][k] 表示 u 的第2k个祖先是谁。很容易就想到递推式:ancestors[j][i]=ancestors[ancestors[j][i-1]][i...
  • 最近公共祖先(LCA) 倍增优化 定义 最近公共祖先(Lowest Common Ancestor):两个节点的公共祖先节点中离根最远(即深度最深)的节点。 性质 uuu是vvv的祖先,当且仅当LCA(u,v)=uLCA(u,v)=uLCA(u,v)=u 如果uuu不为...
  • //循环过程中不加判断可能会超过最近公共祖先,所以跟新到lca的儿子节点即可 return dp[u][0]; } int main() { int n,m,u,v; scanf("%d %d",&n,&m); cnt=0; memset(head,-1,sizeof(head)); for(int i=1; i; +...
  • 洛谷 P3379 【模板】最近公共祖先倍增LCA) 题解: 一道LCA的模板题,用倍增LCA来做再合适不过了~时间复杂度为O(nlogn) 倍增的思想可以用在很多地方,这里就说说如何用倍增来解决LCA的问题吧~ 自己画的图比较丑 ....
  • 如图,3和5的最近公共祖先是1,5和2的最近公共祖先是4 在本篇中我们先介绍一下倍增算法 我们需要一个数组de[i]来表示每一个节点i的深度,用另一数组parent[i][j]来表示每一节点j向上走2的i次方是哪个节点 我们...
  • 给出一颗二叉树的后序遍历和中序遍历,你能计算出两个结点的最近公共祖先吗? 输入格式: 第一行给出两个整数N(N<=10000)和M(M<=10000),分别代表二叉树的结点数和我们接下来的询问数。 第二行和第三行分别给出...
  • 最近公共祖先LCA(倍增) 给定一棵 以 sss 为根节点,共有 nnn 个点的树。 有 mmm 次查询 任意两点 u,vu ,vu,v 的最近公共祖先 一、前置知识点 1.邻接链表 存图 2.倍增原理 ( 2n2^n2n 的预处理应用 ) 二、算法流程 1...
  • 输入格式 第一行输入一个整数 n(2≤n≤10,000),表示树上有 n 个节点。...(1≤q≤1,000) 接下来的 q 行,每行输入俩个整数 c,d(1≤c,d≤n)代表询问 c,d 俩个节点的最近公共祖先。 输出格式 对于每次...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 807
精华内容 322
关键字:

最近公共祖先倍增