LCA
求解 LCA の方法
最近公共祖先（LCA） 最近公共祖先简称 LCA（Lowest Common Ancestor）。两个节点的最近公共祖先，就是这两个点的公共祖先里面，离根最远的那个。 oi wiki 举个例子 在这张图中，$5$ 和 $9$ 的最近公共祖先就是 $3$，$9$ 和 $7$ 的最近公共祖先就是 $2$ ......
P4211 [LNOI2014]LCA
$\color{purple}\text{P4211 [LNOI2014]LCA}$ 解题方法 可以发现一个结论：两个点到根节点的重合路径的长度即为他们 $LCA$ 的深度。所以我们把 $[l,r]$ 之间的点到根节点路径上各加一，再查询 $z$ 到根节点的路径的值之和即为 $\sum_{i=l}^ ......
LCA（最近公共祖先）学习笔记
前言 没想到干完lca的时间比tarjan的还要长（我不能这么弱下去了！！） 前置知识 dfs序 这东西有点类似于时间戳（dfn），但是它分为两部分（回溯之前和回溯之后）。并且dfs序还分为两种。这里只介绍一倍的dfs序。 如上图，蓝色代表左端点，红色代表右端点，（学过Tarjan的都知道），蓝色其 ......
LeetCode 周赛 341 场，模拟 / 树上差分 / Tarjan 离线 LCA / DFS
本文已收录到 AndroidFamily，技术和职场问题，请关注公众号 [彭旭锐] 提问。 大家好，我是小彭。 上周末有单双周赛，双周赛我们讲过了，单周赛那天早上有事没参加，后面做了虚拟竞赛，然后整个人就不好了。前 3 题非常简单，但第 4 题有点东西啊，差点就放弃了。最后，被折磨了一个下午和一个大 ......
LCA——ST表+欧拉序
了解到一个quan新的东西： 用ST表（欧拉序）实现LCA(树上最近公共祖先) 欧拉序 前序遍历得到的序列，叫dfs序 但数字可以重复出现，一进一出，叫欧拉序 会发现根结点总在中间 而根结点是该段序列深度最小的点 因此两个点的LCA， 就是在该序列上两个点第一次出现的区间内深度最小的那个点 即转化为 ......
LCA投票
lca投票是一种用于树状结构中找到最近公共祖先（lca）的算法。在一些应用场景下，需要对n个节点进行m次询问，每次询问给出两个节点x和y，并询问它们的最近公共祖先。lca投票的时间复杂度为o(n+m)，效率较高，因此广泛应用于各种算法竞赛等场合。 lca投票的过程如下：从任意一个节点开始，通过dfs ......
20230412 训练记录：最小生成树 / lca / 一类路径计数
话说今天运气还不错。开盖再来一瓶送可乐的活动连中了三瓶，请队友恰了一元可乐 (╹ڡ╹ )。 严格次小生成树 Exp++ https://www.luogu.com.cn/problem/P4180 https://www.acwing.com/problem/content/358/ https:/ ......
20230411 训练记录：lca / 次小生成树
先打了个 lca 板子，POJ1330，要找一下根： for (int i = 1, u, v; i < n; i++) { scanf("%d%d", &u, &v); link(u, v), link(v, u); d[v] += 1; } int rt = 1; while (d[rt]) r ......
20230410 训练记录：最小瓶颈路 / lca
初识最小瓶颈路其实是上海那道著名的铜牌题，其次就是 P1396 营救。 P1967 [NOIP2013 提高组] 货车运输 / 最小瓶颈路 https://www.luogu.com.cn/problem/P1967 $\mathcal O(m \log m + (n + q)\log n)$ 最大 ......
[LNOI2014] LCA 树链剖分+离线处理+lca转化
困困的开始了我的修炼树剖之旅途 考虑怎么搞这个lca 是说，习惯了倍增求lca，突然冒出这么一个东西还真不会搞 那要么能一次性求很多个lca(?)，要么把deep[lca(i,z)]这个东西转化一下 当我们不会倍增求lca的时候，有一个很朴素的想法就是把x到根节点一路上的点都染色 然后让y节点开始往 ......
做题记录 230328 // LCA
A. 暗的连锁 http://222.180.160.110:1024/contest/3470/problem/1 不难发现树上的边和附加边是两个独立的部分。 若只看所有附加边，对于某一条附加边，当它是这些附加边中的桥时，切断它所连接的两点在树上的简单路径即可达到目的。 于是我深陷于这个思路想了很 ......
SCOI2015 情报传递 主席树+LCA
哈哈哈哈老婆我有出息了，犬犬第一次从思路到代码都是自己一发切了紫题呢~ 好了一眼数据结构。 考虑如何转化第i个时刻有威胁的情报员，若能产生威胁 则说明他们至少在i-c-1这个时刻"出生" 也就是转化为在权值线段树上查询[1,i-c-1]有多少个人。 启发了我们可以先把未来的情报员都弄下来，再记一个他 ......
算法学习笔记(5): 最近公共祖先(LCA)
最近公共祖先(LCA) 最近公共祖先是树上的概念，不了解树的出门左转百度：树（数据结构名词）_百度百科 定义 假设我们需要求 x 和 y 的最近公共祖先，这里有多种等价的定义 路径x到y上深度最小的点 x和y公共祖先中深度最大的点 x和y在这棵树上距离最近的公共祖先结点 如果x就是y的祖先，则x本身 ......