LCA最近公共祖先
- 2022 年 7 月 9 日
- 筆記
最近公共祖先就字面意思，两个节点一起往上跳，找到的最近的公共点 找到u和v第一个不同祖先不同的位置，然后这个位置向上走一步就是最近公共的祖先 但是想找到u,v第一个不同祖先的位置，就要保证u,v在同一深度（才能一起往上移动） 所以这个过程分为三部分， 1. 预处理找到每个节点深度 2. 把较深的一点 …
Continue Reading
P7518 & 省選聯考2021 寶石
- 2021 年 5 月 5 日
- 筆記
这是一篇极其简单连像我这样省三参加不了省选的蒟蒻都能看懂的题解 前置知识： 倍增LCA 二分 栈 题意 PS：这是一篇完全面向初学者的题解，会非常细，大佬请无视 题目传送门 没有思路的时候， 我们往往可以从简单的情况下手， 比如一条链 我们记Pi为第i个需要搜集的宝石， S为起点， T为终点。 不妨 …
Continue Reading
[NOIP2013 提高組] 貨車運輸
- 2020 年 12 月 29 日
- 筆記
前言 使用算法：堆优化 \(prim\) ， \(LCA\) 。 题意 共有 \(n\) 个点，有 \(m\) 条边来连接这些点，每条边有权值。有 \(q\) 条类似于 \(u\) \(v\) 询问，求一条从 \(u\) 到 \(v\) 的路径使得路径上的最小权值最大，求这个最大值。若不存在从 \( …
Continue Reading