C++信奥教学PPT：CSP_S_算法之倍增算法求最近公共祖先（暑假精英班开招）

本 PPT 为 LCA 系列。分别介绍了求最近公共祖先有多种算法思想：

1. 朴素算法 （本章节）。2. 倍增算法（本章节）。3. Tarjan 算法。4. 用欧拉序列转化为 RMQ 问题。5. 树链剖分。LCA 为两个指针跳转到同一条重链上时深度较小的那个指针所指向的点。树链剖分的预处理时间复杂度为 O(n)，单次查询的时间复杂度为 O(log n)，并且常数较小。6. 动态树。设连续两次访问操作的点分别为 u 和 v，则第二次访问操作返回的点即为 u 和 v 的 LCA。在无 link 和 cut 等操作的情况下，使用 link cut tree 单次查询的时间复杂度为 O(log n)。7. 标准 RMQ

子串（Substrings, Asia-Hangzhou 2012, LA6373）给出一个长度为n的数组。需要计算对于给定的w，所有长度为w的子串中的不同元素的个数之和。例如，数组是{1 1 2 3 4 4 5}。当w=3时，有5个长度为3的子串，它们分别是(1, 1, 2),(1, 2, 3),(2, 3, 4),(3, 4, 4),(4, 4, 5)。各自的不同元素的数目是2,3,3,2,2。所以总和就是2+3+3+2+2=12。数据范围：0<w≤n≤106，每一个数组会有Q（0≤Q≤104）个w需要计算，数组中的元素：0≤a1, a2…an≤106。

迷路（Lost, Asia-Jinhua 2012, LA6329）彪哥来游乐园玩，有N（5≤N≤100000）个娱乐设施，还有N条双向道路连接这些设施。你可以从其中任意一个开始然后再到其他的。每到一个设施，他把它标记为已访问。然后在连接到这个设施的未访问设施中选择一个，如果有多个，那么就等概率随机选择。一开始要在N个娱乐设施中随机等概率选择，并且重复这个过程，直到无路可走。计算对于每个设施，彪哥最后一个访问的概率，然后输出5个最大的概率之和，保留小数点后5位。输入的设施和道路形成的图中，显然只会有一个环，输入这个环的长度保证在3～30。