秃头小白

LCA

01背包(1) bfs(4) dfs(6) dfs序讲解(1) Dijkstra算法优先队列优化(2) dp(7) KMP(1) STL(1) 二分(5) 二分图(3) 二进制(1) 二进制枚举(3) 优先队列(1) 倍增(2) 分治(2) 前缀和与差分(3) 区间dp(11) 博弈论(1) 图(1) 并查集(5) 快速幂(1) 思维题(55) 数学题(7) 数论(2) 整除分块（数论）(1) 最小生成树(2) 有关约数（质因数等）的基础数论(2) 栈(1) 树吧(5) 树状dp(1) 树状数组(2) 树状数组+dfs序(2) 模拟(4) 滑动窗口(4) 状压dp(1) 离散化+并查集(1) 离散化讲解及入门例题(2) 签到题(2) 素数筛(1) 线段树(10) 贪心(12) 逆元(1) 逆序对的三种求法(1) 题解(16) 高精度(8)

/ 注册

全部文章 / LCA （共4篇）

CodeForces - 519E A and B and Lecture Rooms

题目链接 https://vjudge.net/problem/CodeForces-519E 解题思路整体思路：LCA 详细思路：前置知识：里面的链接是知识点的讲解具体思路：我们分两种大情况 u==LCA(u,v) || v==LCA(u,v) 小情况1：若u==v，则答案直接就是...

2020-11-29

1 574

[AHOI2008]MEET 紧急集合

题目链接 https://ac.nowcoder.com/acm/problem/20532 解题思路整体思路：考虑每两个节点之间的最短距离就是求这两个点的 LCA ，那么三个点我们可以先两两一组找到 LCA。我们可以发现三个点的 LCA 要么是完全一样，要么是有两个（两个相同，一个不同），如果是...

2020-11-26

1 656

Max Flow P

题目链接 https://www.luogu.com.cn/problem/P3128 解题思路树上差分 LCA知道树上差分在什么情况下使用，树上路径，树上两点等。 AC代码 #include<bits/stdc++.h> using namespace std; const in...

2020-11-25

1 519

P3379 【模板】最近公共祖先（LCA）

题目链接 https://www.luogu.com.cn/problem/P3379 解题思路 ST表 + 欧拉序。通过欧拉序会发现根结点总在中间，而根结点是该段序列深度最小的点。因此两个点的LCA，就是在该序列上两个点第一次出现的区间内深度最小的那个点。细节见代码，主要是注意下标含义。 A...

2020-11-24

1 612