在线查询树上最近公共祖先模板

在线查询树上最近公共祖先

标准题目

第一行有2个整数n和q:n代表树的结点数量,q代表询问的次数接下来n-1行每行两个整数u和v,表示结点u到结点v有一条边。
然后给出q组询问,每组询问由两个整数a和b构成,询问节点a和b的最近公共祖先。

样例数据

input
8 3
1 3
1 2
3 4
3 5
3 6
2 7
2 8
4 5
6 7
5 8

output:
3
1
1

代码

1. 邻接表建图

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <queue>
 6 using namespace std;
 7 const int lim=100000000;
 8 const int maxn=600010;
 9 struct point {
10     int to;
11     int nxt;
12 } edge[maxn*2];
13 int n,Q,tot=0;
14 int dep[maxn]= {0},f[20][maxn];
15 bool vis[maxn];
16 int head[maxn];
17
18 void add(int u,int v) {
19     tot++;
20     edge[tot].to=v;
21     edge[tot].nxt=head[u];
22     head[u]=tot;
23 }
24
25
26 int Lca(int x,int y) { //lca
27     int temp,co=0,lca;
28     int tx=x,ty=y;
29     if(dep[tx]>dep[ty]) swap(tx,ty);
30     temp=dep[ty]-dep[tx];
31     while(temp) {
32         if(temp&1) ty=f[co][ty];
33         temp>>=1;
34         co++;
35     }
36     if(tx==ty) return tx;
37     else {
38         for(int j=19; j+1; j--) {
39             if((1<<j)>dep[tx]) continue;
40             if(f[j][tx]!=f[j][ty]) {
41                 tx=f[j][tx];
42                 ty=f[j][ty];
43             }
44         }
45         lca=f[0][tx];
46     }
47     return lca;
48 }
49 inline void bfs() {
50     queue<int> q;
51     vis[1]=1;
52     dep[1]=0;
53     q.push(1);
54     while(!q.empty()) { //宽搜处理dep和f[0][i] (父节点)
55         int tt=q.front();
56         q.pop();
57         for(int i=head[tt]; i; i=edge[i].nxt) {
58             int v=edge[i].to;
59             if(!vis[v]) {
60                 vis[v]=1;
61                 q.push(v);
62                 dep[v]=dep[tt]+1;
63                 f[0][v]=tt;
64             }
65         }
66     }
67 }
68 int main() {
69     memset(head,0,sizeof(head));
70     cin>>n>>Q;
71     for(int i=1; i<=n-1; i++) {
72         int a,b;
73         cin>>a>>b;
74         add(a,b);//双向建图
75         add(b,a);
76     }
77
78     bfs();
79     for(int j=1; j<20; j++) //倍增
80         for(int i=1; i<=n; i++)
81             if(dep[i]>=(1<<j))
82                 f[j][i]=f[j-1][f[j-1][i]];
83     while(Q--) {
84         int a,b,lca;
85         cin>>a>>b;
86         lca=Lca(a,b);
87         cout<<lca<<endl;
88     }
89
90     return 0;
91 }

2. Vector建图

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn=600010;

int n,Q,tot=0;
int depth[maxn]= {0},f[20][maxn];
bool vis[maxn];
int head[maxn];
vector<int> edge[maxn];

void add(int u,int v) {
    edge[u].push_back(v);
}

int Lca(int x,int y) { //lca
    int temp,co=0,lca;
    int tx=x,ty=y;
    if(depth[tx]>depth[ty]) swap(tx,ty);
    temp=depth[ty]-depth[tx];
    while(temp) {
        if(temp&1) ty=f[co][ty];
        temp>>=1;
        co++;
    }
    if(tx==ty) return tx;
    else {
        for(int j=19; j+1; j--) {
            if((1<<j)>depth[tx]) continue;
            if(f[j][tx]!=f[j][ty]) {
                tx=f[j][tx];
                ty=f[j][ty];
            }
        }
        lca=f[0][tx];
    }
    return lca;
}
inline void bfs() {
    queue<int> q;
    vis[1]=1;
    depth[1]=0;
    q.push(1);
    while(!q.empty()) { //宽搜处理depth和f[0][i]
        int now=q.front();
        q.pop();
        int len=edge[now].size();
        for(int i=0; i<len; i++) {
            int v=edge[now][i];
            if(!vis[v]) {
                vis[v]=1;
                q.push(v);
                depth[v]=depth[now]+1;
                f[0][v]=now;
            }
        }
    }
}
int main() {
    memset(head,0,sizeof(head));
    cin>>n>>Q;
    for(int i=1; i<=n-1; i++) {
        int a,b;
        cin>>a>>b;
        add(a,b);//双向建图
        add(b,a);
    }

    bfs();
    for(int j=1; j<20; j++) //倍增
        for(int i=1; i<=n; i++)
            if(depth[i]>=(1<<j))
                f[j][i]=f[j-1][f[j-1][i]];
    while(Q--) {
        int a,b,lca;
        cin>>a>>b;
        lca=Lca(a,b);
        cout<<lca<<endl;
    }

    return 0;
}
时间: 07-22

在线查询树上最近公共祖先模板的相关文章

【LCA】0.1单组不会倍增的暴力的树上最近公共祖先

0.1就是0.1……弱的不行……只是暂时存一下为以后高大上的正解作铺垫 Q:LCA都不会你学什么OI? A:我学不了OI了我要滚粗…… 适当解释: 第一行输入点数n以及两个要查询的点q1,q2 第二行输入每个点父亲father[i] 一行输出ans==最近公共祖先…… 不会倍增……写了个看起来是正解其实是暴力的东东…… #include<iostream> #include<cstdlib> #include<cstdio> using namespace std; i

树上最近公共祖先(LCA)的算法

有错请大力指出[鞠躬]第一次写正经博客非常慌张 LCA(Least Common Ancestors),即最近公共祖先,是指在有根树中,找出某两个结点u和v最近的公共祖先. 对于有根树T的两个结点u.v,最近公共祖先LCA(T,u,v)表示一个结点x,满足x是u.v的祖先且x的深度尽可能大. 另一种理解方式是把T理解为一个无向无环图,而LCA(T,u,v)即u到v的最短路上深度最小的点. --百度百科 LCA的四种算法: 记录dfs序转化为rmq问题(st表) tarjan算法 倍增算法 树链剖

lca最短公共祖先模板(hdu2586)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2586 #include<iostream> #include<cstdio> #include<cmath> #include<queue> #include<vector> #include<string.h> #include<cstring> #include<algorithm> #include<s

9018:1892:最近公共祖先

题目描述 编写一个程序,查找一棵含有n个节点的树中m组两个不同节点的最近公共祖先. 输入 第一行两个整数n和q,为树上节点的数目和查询数.节点标号为整数 1,2,...,n.之后n-1行每一行包含一对整数,代表边--第一个整数是第二个整数的父节点.请注意,一个具有n个节点的树有n-1条边.之后q行查询,每行两个整数,表示要查询的两个节点的标号.(输入保证有且只有一棵树) 输出 q行,每行一个整数,为此次查询的最近公共祖先的标号 样例输入 5 6 2 5 2 3 5 1 1 4 1 3 2 3 5

图论-最近公共祖先-在线树上倍增

有关概念: 最近公共祖先(LCA,Lowest Common Ancestors):对于有根树T的两个结点u.v,最近公共祖先表示u和v的深度最大的共同祖先. 树上倍增是求LCA的在线算法(对于每一个询问输入后即计算) 思路: fa[i][j]表示编号为j的结点从下往上的第2i个祖先 即fa[0][j]表示j的父结点,递推式为fa[i][j]=fa[i-1][fa[i-1][j]],即j的第2i个祖先为j的第2i-1个祖先的第2i-1个祖先 另:不存在第2i个祖先(即2i超过j的深度)时,f[i

hihoCoder_#1069_最近公共祖先&#183;三(RMQ-ST模板)

#1069 : 最近公共祖先·三 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 上上回说到,小Hi和小Ho使用了Tarjan算法来优化了他们的"最近公共祖先"网站,但是很快这样一个离线算法就出现了问题:如果只有一个人提出了询问,那么小Hi和小Ho很难决定到底是针对这个询问就直接进行计算还是等待一定数量的询问一起计算.毕竟无论是一个询问还是很多个询问,使用离线算法都是只需要做一次深度优先搜索就可以了的. 那么问题就来了,如果每次计算都只针对一个询问进行的话

hihoCoder_#1067_最近公共祖先&#183;二(LCA模板)

#1067 : 最近公共祖先·二 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 上上回说到,小Hi和小Ho用非常拙劣--或者说粗糙的手段山寨出了一个神奇的网站,这个网站可以计算出某两个人的所有共同祖先中辈分最低的一个是谁.远在美国的他们利用了一些奇妙的技术获得了国内许多人的相关信息,并且搭建了一个小小的网站来应付来自四面八方的请求. 但正如我们所能想象到的--这样一个简单的算法并不能支撑住非常大的访问量,所以摆在小Hi和小Ho面前的无非两种选择: 其一是购买更为昂

最近公共祖先(LCA):离线&amp;在线算法

问题:求两个结点的最近公共祖先(即在树中的公共祖先中高度最低的祖先),下面介绍两种适用于不同场景的算法. Hiho15:离线Tarjan算法 基本思想 Tarjan算法适用于离线批量处理多个查询请求.基本思想是以深度优先搜索的顺序访问这颗树,给这棵树的结点染色,一开始所有结点都是白色的,而当第一次经过某个结点的时候,将它染成灰色,而当第二次经过这个结点的时候--也就是离开这棵子树的时候,将它染成黑色. 这样做的意义,举例说明,当我们深度优先搜索到A结点时,我们发现A结点和B结点是我们需要处理的一

连通分量模板:tarjan: 求割点 &amp;&amp; 桥 &amp;&amp; 缩点 &amp;&amp; 强连通分量 &amp;&amp; 双连通分量 &amp;&amp; LCA(最近公共祖先)

PS:摘自一不知名的来自大神. 1.割点:若删掉某点后,原连通图分裂为多个子图,则称该点为割点. 2.割点集合:在一个无向连通图中,如果有一个顶点集合,删除这个顶点集合,以及这个集合中所有顶点相关联的边以后,原图变成多个连通块,就称这个点集为割点集合. 3.点连通度:最小割点集合中的顶点数. 4.割边(桥):删掉它之后,图必然会分裂为两个或两个以上的子图. 5.割边集合:如果有一个边集合,删除这个边集合以后,原图变成多个连通块,就称这个点集为割边集合. 6.边连通度:一个图的边连通度的定义为,最