首页 > 其他分享 >Lca最近公共祖先（非常实用）

Lca最近公共祖先（非常实用）

时间：2024-11-01 19:21:12浏览次数：6  
标签：dep fa 祖先 实用 int pa Lca include 10

一般求lca的方式就是基于下面的模板，中间的过程就不推理了，有兴趣可以去听听y总的课，讲的很详细

模板题

给定一棵包含 n 个节点的有根无向树，节点编号互不相同，但不一定是 1∼n。

有 m 个询问，每个询问给出了一对节点的编号 x 和 y，询问 x 与 y 的祖孙关系。

输入格式

输入第一行包括一个整数 表示节点个数；

接下来 n 行每行一对整数 a 和 b，表示 a 和 b 之间有一条无向边。如果 b 是 −1，那么 aa 就是树的根；

第 n+2 行是一个整数 m 表示询问个数；

接下来 m 行，每行两个不同的正整数 x 和 y，表示一个询问。

输出格式

对于每一个询问，若 x 是 y 的祖先则输出 1，若 y 是 x 的祖先则输出 2，否则输出 0。

数据范围

1≤n,m≤4×10^4
1≤每个节点的编号≤4×10^4

输入样例：

10
234 -1
12 234
13 234
14 234
15 234
16 234
17 234
18 234
19 234
233 19
5
234 233
233 12
233 13
233 15
233 19

输出样例：

1
0
0
0
2

代码

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>

using namespace std;

const int N = 4e4 + 10;
int dep[N];
int fa[N][16];
vector<int> e[N];

int n, m;
int x, y;

void bfs(int root){
    memset(dep,0x3f,sizeof(dep));
    
    queue<int> q;
    q.push(root);
    dep[0] = 0, dep[root] = 1;
    
    while(!q.empty()){
        auto t = q.front();
        q.pop();
        
        for(auto x : e[t]){
            if(dep[t] + 1 < dep[x]){
                dep[x] = dep[t] + 1;
                fa[x][0] = t;
                for(int i = 1;i <= 15;i ++){
                    fa[x][i] = fa[fa[x][i - 1]][i - 1];
                }
                q.push(x);
            }
        }
    }
}

int lca(int a, int b){
    if(dep[a] < dep[b]) swap(a, b);
    
    for(int i = 15;i >= 0;i --){
        if(dep[fa[a][i]] >= dep[b]) a = fa[a][i];
    }
    if(a == b) return a;
    for(int i = 15;i >= 0;i --){
        if(fa[a][i] != fa[b][i]){
            a = fa[a][i];
            b = fa[b][i];
        }
    }
    return fa[a][0];
}

int main()
{
    cin >> n;
    int root = 0;
    for(int i = 0,A,B;i < n;i ++){
        cin >> A >> B;
        if(B == -1) root = A;
        else e[A].push_back(B), e[B].push_back(A);
    }
    
    bfs(root);
    
    cin >> m;
    while(m --){
        cin >> x >> y;
        if(lca(x,y) == x) cout << 1 << endl;
        else if(lca(x,y) == y) cout << 2 << endl;
        else cout << 0 << endl;
    }
    
    return 0;
}

这是用bfs初始化的模板，下面给出用dfs初始化的模板

1171.距离

给出 n 个点的一棵树，多次询问两点之间的最短距离。

注意：

  • 边是无向的。
  • 所有节点的编号是 1,2,…,n

输入格式

第一行为两个整数 n 和 m。n 表示点数，m 表示询问次数；

下来 n−1 行，每行三个整数 x,y,k，表示点 x 和点 y 之间存在一条边长度为 k；

再接下来 m 行，每行两个整数 x,y，表示询问点 x 到点 y 的最短距离。

树中结点编号从 1 到 n。

输出格式

共 m 行，对于每次询问，输出一行询问结果。

数据范围

2≤n≤10^4
1≤m≤2×10^4
0<k≤100
1≤x,y≤n

输入样例1：

2 2 
1 2 100 
1 2 
2 1

输出样例1：

100
100

输入样例2：

3 2
1 2 10
3 1 15
1 2
3 2

输出样例2：

10
25


这题没有那么素，但是也很模板了，大致思路说下，一般来说两点最短路想到的会是dijkstra，但是这道题不适合，因为数据范围大，如果只查询一次那dijkstra非常合适。那么就要先预处理好所有点到根节点的距离，那么如果pa是a和b的最近公共祖先则a和b的最短距离就是dist[a]+dist[b] - 2*dist[pa]

代码

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>

using namespace std;

typedef pair<int,int> PII;

const int N = 1e4 + 10;
int fa[N][16];
int dep[N], dist[N];
vector<PII> e[N];

int n, m;

void dfs(int u,int pa){
    dep[u] = dep[pa] + 1;
    fa[u][0] = pa;
    for(int i = 1;i <= 14;i ++){
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }
    
    for(auto [x, w] : e[u]){
        if(x == pa) continue;
        dist[x] = dist[u] + w;
        dfs(x, u);
    }
}

int lca(int a, int b){
    if(a == b) return a;
    
    if(dep[a] < dep[b]) swap(a, b);
    
    for(int i = 14;i >= 0;i --){
        if(dep[fa[a][i]] >= dep[b]){
            a = fa[a][i];
        }
    }
    if(a == b) return a;
    
    for(int i = 14;i >= 0;i --){
        if(fa[a][i] != fa[b][i]){
            a = fa[a][i];
            b = fa[b][i];
        }
    }
    return fa[a][0];
}

int main()
{
    cin >> n >> m;
    for(int i = 0,u,v,w;i < n - 1;i ++){
        cin >> u >> v >> w;
        e[u].push_back({v,w}), e[v].push_back({u,w});
    }
    
    dep[0] = 0;
    dfs(1, 0);
    
    while(m --){
        int a, b;
        cin >> a >> b;
        int pa = lca(a, b);
        int dis = dist[a] + dist[b] - 2 * dist[pa];
        cout << dis << endl;
    }
    
    return 0;
}

下面就是应用了

D. Paint the Tree（Lca + 树的直径）

传送门：Problem - D - Codeforces

378QAQ has a tree with nn vertices. Initially, all vertices are white.

There are two chess pieces called PAPA and PBPB on the tree. PAPA and PBPB are initially located on vertices aa and bb respectively. In one step, 378QAQ will do the following in order:

  1. Move PAPA to a neighboring vertex. If the target vertex is white, this vertex will be painted red.
  2. Move PBPB to a neighboring vertex. If the target vertex is colored in red, this vertex will be painted blue.

Initially, the vertex a is painted red. If a=b, the vertex a is painted blue instead. Note that both the chess pieces must be moved in each step. Two pieces can be on the same vertex at any given time.

378QAQ wants to know the minimum number of steps to paint all vertices blue.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤10^4). The description of the test cases follows.

The first line of each test case contains one integer n (1≤n≤2⋅10^5).

The second line of each test case contains two integers a and b (1≤a,b≤n).

Then n−1 lines follow, each line contains two integers xi and yi (1≤xi,yi≤n), indicating an edge between vertices xi and yi. It is guaranteed that these edges form a tree.

It is guaranteed that the sum of nn over all test cases does not exceed 2⋅10^5

Output

For each test case, output the minimum number of steps to paint all vertices blue.

题目大意

给出一棵树，每个点初始为白色。Alice 在 PA​，Bob 在 PB​。每次操作两人需要移动到相邻的结点，Alice 会将脚下的白点染成红色，Bob 会将脚下的红点染成蓝色。

求将整棵树染成蓝色的最小操作次数。

我个人认为一般跟树的直径相关的题，还是比较难的，至少代码是真的难写。不了解树的直径的可以看看 树与图的深度优先遍历（dfs的图论中的应用）_有向图深度优先遍历例题-CSDN博客

对于这个问题我们就假设么，最差情况是怎么样的，那就是 a 先涂一遍 n 步， b 在涂一遍 n 步。最差情况就是2 * n了，那么我们假设在a 还没涂完全图的时候他们相遇了， 剩下的步子只要 b 跟着 a 走了，就比如走了 x 步吧，那是不是就省了 x 步，b 第二遍涂的时候就可以不用去涂之前涂过的 x 个格子了。那就找到子问题了，求最大的 x

这里呢比较难想。主要还是对树的直径敏不敏感。肯定我们首先要让a 和 b先相遇么，这个很容易想到 Lca（pa） 但是相遇的点一定就是 pa 吗？能不能保证之后走的格子数最大，不行。应该把此路径当作树的直径然后找中心点，这样就一定保证之后走的最大，可以画图想想。那么还有一个问题如果路径数是偶数那说明他们不能同时到那个中心点，那么我们就先走 add 步，然后让他们的的下一个点是同一个点距离是1，然后再走一步就可以相遇了。然后把 add 加上把 x 减掉就行了

代码 

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>

using namespace std;

const int N = 2e5 + 10;
int dep[N];
int fa[N][22];
vector<int> e[N];

int t;
int n, A, B;

void dfs(int u,int pa){
    dep[u] = dep[pa] + 1;
    fa[u][0] = pa;
    for(int i = 1;i <= 19;i ++){
        fa[u][i] = fa[fa[u][i - 1]][i - 1];
    }

    for(auto x : e[u]){
        if(x == pa) continue;
        dfs(x, u);
    }
}

int lca(int a, int b){
    if(a == b) return a;

    if(dep[a] < dep[b]) swap(a, b);
    for(int i = 19;i >= 0;i --){
        if(dep[fa[a][i]] >= dep[b]){
            a = fa[a][i];
        }
    }
    if(a == b) return a;

    for(int i = 19;i >= 0;i --){
        if(fa[a][i] != fa[b][i]){
            a = fa[a][i];
            b = fa[b][i];
        }
    }

    return fa[a][0];
}

void dfs1(int u,int pa){
    dep[u] = dep[pa] + 1;
    for(auto x : e[u]){
        if(x == pa) continue;
        dfs1(x, u);
    }
}

void solve()
{
    cin >> n >> A >> B;
    for(int i = 1;i <= n;i ++){
        e[i].clear(), dep[i] = 0;
        for(int j = 0;j < 22;j ++){
            fa[i][j] = 0;
        }
    }
    for(int i = 0,x,y;i < n - 1;i ++){
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }

    dfs(1, 0);
    int pa = lca(A, B);
    // cout << pa << endl;
    vector<int> p1, p2;
    int cur = A;
    while(cur != pa){
        p1.push_back(cur);
        cur = fa[cur][0];
    }
    p1.push_back(pa);
    cur = B;
    while(cur != pa){
        p2.push_back(cur);
        cur = fa[cur][0];
    }
    for(int i = p2.size() - 1;i >= 0;i --) p1.push_back(p2[i]);
    // for(int i = 0;i < p1.size();i ++) cout << p1[i] << " ";
    // cout << endl;
    int add = (p1.size() - 1) / 2 + (p1.size() % 2 == 0), center = p1[(p1.size() - 1) / 2];
    // cout << add << " " << center << endl;
    dfs1(center, 0);
    int mx = -1;
    for(int i = 1;i <= n;i ++) mx = max(mx, dep[i]);
    cout << (n - 1) * 2 - mx + add + 1 << endl;
}

int main()
{
    cin >> t;
    while(t --){
        solve();
    }
    return 0;
}

加油

标签：dep,fa,祖先,实用,int,pa,Lca,include,10
From： https://blog.csdn.net/AuRoRamth/article/details/143438855

相关文章

  • 在Spring中实现事件发布与监听：实用指南
    Spring框架事件机制的背景和重要性背景解耦设计：在复杂的应用程序中，组件之间的紧密耦合会导致代码难以维护和扩展。事件机制提供了一种解耦的方式，允许组件通过事件进行通信，而无需直接依赖。异步处理：事件机制支持异步处理，可以在不阻塞主线程的情况下处理耗时操作，提高应用的......
  • 百度SEO分析实用指南 提升网站搜索排名的有效策略
    内容概要在数字化时代，搜索引擎优化（SEO）已经成为提升网站曝光度的关键工具。本指南将带您了解SEO的基本知识，帮助您在复杂的网络环境中立足。我们将从关键词优化开始，重点讲解如何选择合适的关键词来提高搜索引擎排名。随后，我们将探讨网站结构调整的重要性，包括如何提升页面加载速......
  • 电脑如何远程监控另一台电脑？分享3个简单实用的小妙招，一分钟轻松掌握！
    在数字化时代，远程监控另一台电脑已成为企业管理、技术支持以及共享资源等场景下的常见需求。那么，电脑如何远程监控另一台电脑？今天，我们就来分享三个简单实用的小妙招，教你如何轻松实现电脑对另一台电脑的远程监控。妙招一：使用Windows远程桌面连接对于使用Windows操作系统的......
  • 用三剑客来快速进行uuid挂载方法.很实用,可以先在虚拟机上试试看,不好用欢迎评论区来
    blkid|grep'UUID'|sed-n'5p'|sed-E's/.*UUID="([^"]+)".*/\1/'|xargs-I{}echo"UUID={}/mnt/disk1xfsdefaults00">>/etc/fstab  简单的脚本详细解释在下面:1.blkid-功能：列出系统中所有块设备的UUID、类型等......
  • 超实用！教你用 Python 获取并下载美股数据
     yfinance是一个使用Yahoo!获取数据的Python第三方模块。它支持获取最细到1分钟级的历史数据及股票基本面数据，是免费获得美股分钟级及以上粒度数据的不二之选。如果你正在学习Python并且找不到方向的话可以试试我这一份学习方法+籽料呀！点击领取（不要米米）1.准备请......
  • Comfyui 局部重绘 3种实用技巧
    1、VAE内补编码器例如：想要只改变图像中女孩头发颜色，如果不想写提示词的小伙伴，可以通过提示词反推插件，反推出提示词，然后复制到正向提示词框内，（这里其实可以直接连接到正向提示词，在排除标签栏填上需要排除的提示词就OK，不用复制）去掉以前头发颜色的提示词，加入新的头发颜色提示......
  • 上位机开发01-实用网站合集
    @目录1.工具网站合集2.技术类合集1.技术网站2.C++3.计算机相关4.Java5.前端6.Net1.NET博主2.WPF3.C#4.NETCore7.Git8.Vue收藏夹里有很多好用的网站，分类整理下，方便日后使用。1.工具网站合集阿里巴巴图标库：图标资源。pexels：壁纸、视频。unsplash：壁纸。pixabay：壁纸。No......
  • 公路工程施工项目管理软件有哪个比较实用的
    比较实用的公路工程施工项目管理软件：1、泛普公路工程项目管理软件；2、BentleyProjectWise；3、Aconex；4、公路君数智建造；5、象辑建筑云图。其中，泛普公路工程项目管理软件提供全面的项目计划、进度管理、资源管理和成本管理功能，帮助管理人员有效地规划、跟踪和控制工程项目。1、泛......
  • Rust 跨平台应用开发第一章：快速上手 Rust——实用示例
    1.3实用示例在这一节中，我们将通过一系列实用的示例来帮助您更好地理解Rust的特性，并展示如何在实际项目中使用这些特性。示例将涵盖文件操作、网络请求、并发编程、命令行工具以及使用Cargo管理依赖等多个方面。1.3.1文件操作示例Rust提供了强大的标准库来进行文件操......
  • 一个包含了超过 200 个实用脚本的 Python 脚本库，如文件管理、网络操作、图像处理、文
    前言在日常的工作和生活中，我们经常会遇到一些重复性的任务，如文件管理、网络cao作、图像处理、文本处理等。这些任务虽然简单，但如果频繁手动cao作，不仅耗时耗力，还容易出错。现有的软件虽然能处理一部分问题，但往往功能单一，无法满足多样化的需求。那么，有没有一款软件能够处理这种......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99