Luogu P3379 【模板】最近公共祖先(LCA),树链剖分求LCA模板

举报
小哈里 发表于 2022/08/20 00:24:31 2022/08/20
【摘要】 Problem 题目描述 如题,给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先。 输入格式 第一行包含三个正整数 N,M,SN,M,S,分别表示树的结点个数、询问的个数和树根结点的序号。 接...

Problem

题目描述
如题,给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先。

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

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

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

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

输入输出样例
输入 #1复制
5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5
输出 #1复制
4
4
1
4
4
说明/提示
对于 30%30% 的数据,N\leq 10N≤10,M\leq 10M≤10。

对于 70%70% 的数据,N\leq 10000N≤10000,M\leq 10000M≤10000。

对于 100%100% 的数据,N\leq 500000N≤500000,M\leq 500000M≤500000。

样例说明:

该树结构如下:

第一次询问:2, 42,4 的最近公共祖先,故为 44。

第二次询问:3, 23,2 的最近公共祖先,故为 44。

第三次询问:3, 53,5 的最近公共祖先,故为 11。

第四次询问:1, 21,2 的最近公共祖先,故为 44。

第五次询问:4, 54,5 的最近公共祖先,故为 44。

故输出依次为 4, 4, 1, 4, 44,4,1,4,4。

2021/10/4 数据更新 @fstqwq:应要求加了两组数据卡掉了暴力跳。

Codes

  • 留个备忘
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
#define IOS ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
const int maxn = 5e5+10;

int n, q, rt;
struct tree{
    vector<int>G[maxn];
    int fa[maxn], siz[maxn], son[maxn], top[maxn], dep[maxn];
    void add(int x, int y){ 
        G[x].push_back(y); 
        G[y].push_back(x);
    }
    void dfs(int x, int f){
        siz[x] = 1;
        for(int y : G[x]){
            if(y==f)continue;
            fa[y] = x;
            dep[y] = dep[x]+1;
            dfs(y,x);
            if(siz[y] > siz[son[x]])son[x] = y;//x的重儿子
            siz[x] += siz[y];
        }
    }
    void dfs(int x, int y, int f){       //轻重链剖分
        top[x] = y;                      //所在链链顶
        if(son[x])dfs(son[x], y,x);      //重链往下去不用更新链顶
        for(int y : G[x]){
            if(y==f)continue;
            if(y==son[x])continue;
            dfs(y,y,x);                  //更新y为链顶 
        }
    }
    //LCA复杂度:暴力O(n), 倍增O(logn~nlogn), TarjianO(logn~n), 树剖O(logn)
    int lca(int x, int y){
        while(top[x] != top[y]){    //不在同一条链上 每次链顶深度较大的点往上爬
            if(dep[top[x]] < dep[top[y]])swap(x,y);
            x = fa[top[x]];         //进入新的链
        }
        if(dep[x] < dep[y])return x;//进入同一条链上时, 深度小的点在前面
        return y;
    }
    void do_lca(int rt){
        dfs(rt,-1);
        dfs(rt,-1,-1);
    }
}treea;

int main(){
    IOS;
    cin>>n>>q>>rt;
    for(int i = 2; i <= n; i++){
        int u, v;  cin>>u>>v;
        treea.add(u,v);
    }
    treea.do_lca(rt);
    for(int i = 1; i <= q; i++){
        int u, v;  cin>>u>>v;
        cout<<treea.lca(u,v)<<"\n";
    }
    return 0;
}


  
 
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64

文章来源: gwj1314.blog.csdn.net,作者:小哈里,版权归原作者所有,如需转载,请联系作者。

原文链接:gwj1314.blog.csdn.net/article/details/126393245

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

举报
请填写举报理由
0/200