LCA
倍增求lca
步骤： 1.前置准备：lg数组，depth数组，fa数组 2.若x与y不在同一深度，先让它们跳到同一深度 3.开始倍增往上跳 代码： #include<iostream> #include<cstdio> using namespace std; const long long N=1e6+10; ......
P2633 Count on a tree 题解（外加DFS序求LCA）
`2023-07-22 09:53:59 顶置3` # P2633 Count on a tree ## 前置小知识 # 冷门小科技:DFS-RMQ 求LCA 最近跟着洛谷榜一的博客学了一个冷门科技：DFS序求LCA，这道题刚好要求LCA，所以就刚好适用一下。 [$\color{Red}{原博客地址 ......
LeetCode 周赛上分之旅 #44 同余前缀和问题与经典倍增 LCA 算法
> ⭐️ **本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 \[彭旭锐] 和 [BaguTree Pro](https://www.mdnice.com/writing/85b28c4e60354865a423728e668fc570) 知识星球提问。** > > 学习数据 ......
DFS 序求 LCA
## 写在前面 学习于 [skip2004](https://www.cnblogs.com/skip2004/p/12240164.html) 和 [Alex-Wei](https://www.cnblogs.com/alex-wei/p/DFN_LCA.html) 的博客。 DFS 序吊打欧拉序 ......
【算法学习笔记】DFN序求LCA（最近公共祖先）
## 前置知识 * DFN序：对一棵树进行深度优先搜索`DFS`得到的**结点序列**，即深度优先搜索`DFS`的访问顺序。该表述不一定严谨，建议百度 * ST表（Sparse Table，稀疏表） ## 算法概述 > ###引理 1.1 > 在 DFN序 中祖先一定出现后代之前。 考虑一树上的两个 ......
P3629 巡逻 LCA题解
原题：[洛谷P3629](https://www.luogu.com.cn/problem/P3629) ## 问题转化 首先，给定的图是一个有 $n$ 个点，$n-1$ 条边的无向连通图，这个图就等价于一棵树。 不建立新的道路时，从 $1$ 号节点出发，把整棵树上的每条边遍历至少一次，再回到 $1 ......
P3629 巡逻 LCA题解
原题：[洛谷P3629](https://www.luogu.com.cn/problem/P3629) ## 问题转化 首先，给定的图是一个有 $n$ 个点，$n-1$ 条边的无向连通图，这个图就等价于一棵树。 不建立新的道路时，从 $1$ 号节点出发，把整棵树上的每条边遍历至少一次，再回到 $1 ......
[YsOI2023] 广度优先遍历 逆向输出路径(分层建树拓扑序. LCA)
今天的模板测试是无向图上的广度优先遍历，【数据删除】马上写好了代码： 1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 #include <vector> 6 #includ ......
【图论】最近公共祖先（LCA）
## 什么是LCA 最近公共祖先是相对于两个节点来说的，顾名思义，最近公共祖先即为两个节点公共的最近的祖先。 ](https://www.luogu.com.cn/problem/P3379) ## 1.1 常用简短版本（利用结点深度) ```cpp #include #inc ......
最近公共祖先（LCA）
> 「观前提醒」 > > 「文章仅供学习和参考，如有问题请在评论区提出」 [toc] ## 前言 简单的模板整理，只是概括了一下具体的实现方法（说到底是给自己写的），如果看不明白可以去看原视频（讲的很好），链接在参考资料里。 ## 定义 **最近公共祖先**简称 $LCA$（`Lowest Comm ......
LCA
[toc] # LCA最近公共祖先 最近公共祖先简称 LCA（Lowest Common Ancestor）。两个节点的最近公共祖先，就是这两个点的公共祖先里面，离根最远的那个。 暴力求解太慢，这里先摘记一种做法-**倍增法**。 对于每一个节点，我们先通过**dfs预先处理**出当前节点向根移动2 ......
luogu P4592 [TJOI2018] 异或 题解【可持久化01trie+LCA+dfs序】
[TOC] # 题目链接 [P4592 [TJOI2018] 异或](https://www.luogu.com.cn/problem/P4592) # 解题思路 读完题目首先发现很像最大异或和问题 但是在树上操作 一开始想到树剖 但是树剖有两个 $\log$ ~~但是树剖常数小~~ 考虑`dfs` ......
模板 最近公共祖先（LCA）
```c++ void dfs(int u, int v) {//求出每个结点的深度1 dep[u] = dep[p] + 1; fa[u][0] = p; for(int i = 1; (1 = 0; i--) {//i的初始值由节点数确定 if(dep[u] - (1 = dep[v]) { u ......
2167 - 树的公共祖先（LCA）
题目描述 给定一棵树和两个不同的结点，求出他们最近的公共祖先父结点。 已知该树有 n 个结点，标号 1..n 。 输入 第 1 行输入一个整数 nn，代表结点数量（n≤100） 第 2 行输入两个整数 x,yx,y，表示需要计算的结点； 以下 n−1 行，每行两个整数 a 和 b，表示 a 的父结点 ......
P3379 【模板】最近公共祖先（LCA）
## [$P3379$ 【模板】最近公共祖先（$LCA$）](https://www.luogu.com.cn/problem/P3379) #### $LCA$常见的四种求法  LCA，Least Common Ancestors，最近公共祖先。 倍增。 首先预处理出数组 $d_i$ ......
冷门科技 —— DFS 序求 LCA
- Update on 2023.7.17：该技巧目前已知的最早来源：[skip2004](https://www.cnblogs.com/skip2004/p/12240164.html)。 - Update on 2023.7.17：比较时，取时间戳较小的结点也是正确的，不用记录深度。 DFS ......
最近公共祖先(LCA)
# 最近公共祖先(LCA) ## 主要思路：一个节点的$2^n$的祖先是那个节点$2^{n-1}$的祖先的$2^{n-1}$的祖先 ## 也就是说$f[x][n]=f[f[x][n-1]][n-1]$ ## 还要计算$log_2$的值，记录深度 ```c++ #include using names ......
[算法学习笔记] Tarjan LCA
在讲解之前，我们先来看一道模板题：[Luogu P3379 最近公共祖先（LCA)](https://www.luogu.com.cn/problem/P3379) ### What is LCA LCA,即最近公共祖先。什么意思呢，我们举个例子：  { int n, m, s; scanf("%d%d%d", &n, &m, &s); int N = 20; vector> adj(n + 1); for (int i = 1; i dep(n + ......
1151 LCA in a Binary Tree
题目： The lowest common ancestor (LCA) of two nodes U and V in a tree is the deepest node that has both U and V as descendants. Given any two nodes in a ......
tarjan求LCA
最近又重新回顾了下tarjan离线算法求LCA，算是明白是什么意思了，在博客园发现很多文章并没有图，所以这里画个图来帮助还没有理解的人，也算是自己巩固下 LCA 首先我们还是来回顾下什么是LCA 就是最近公共祖先，即a,b的最近公共祖先既是a的祖先，也是b的祖先，况且是a,b的所有公共祖先里面离a和 ......