例题引入
给定一个有 \(n\) 个节点的树,然后有 \(q\) 次询问,每次询问两个节点 \(u, v\) 的 \(\rm{LCA}\) 。
\(1 \leq n \leq 3 \times 10^5, 1 \leq q \leq 10^7\)
讲解
可以发现,倍增和树剖都会 \(\rm{TLE}\) ,因为每次询问都是 \(O(\log_2 n)\) 。
欧拉序
构造方法
实际上是一个比较特殊的 \(\rm{dfs}\) 序。
区别于普通的 \(\rm{dfs}\) 序,除了进入某个节点的时候加入一次序列,回溯到某个节点也会加入到序列,在这里写出伪代码(不想写C++)。
其中 \(A.\mathrm{append}(u)\) 就是向序列末尾添入一个节点 \(u\) 。\(bg_u\) 表示节点 \(u\) 在序列 \(A\) 中首次出现的位置。
性质
可以发现,对于任意一个节点 \(u\), 其在序列中出现的次数是其儿子个数加一,那么通过简单的计算可以得到第一条性质:
另一个比较显然但是很重要的性质:
还有一个在本文用到的性质:
对于两个节点 \(u, v (bg_u \leq bg_v)\),他们的 \(\rm{LCA}\) 一定是 \(A\) 的区间 \([bg_u, bg_v]\) 中 \(dep\) 最小的。正确性比较显然。
主要过程和程序实现
可以首先构建一个 \(\rm{ST}\) 表,记录下大小为 \(2\) 的幂的区间的 \(dep\) 最小的 \(A_i\) ,然后在每次询问的时候找区间 \([bg_u, bg_v]\) 中最小的 \(dep\) 所在的位置。(代码可能有错)
int A[maxn << 1], A_sz, bg[maxn], dep[maxn];
void dfs(int u, int fa) {
A[++A_sz] = u, bg[u] = A_sz, dep[u] = dep[fa] + 1;
for (int i = hd[u]; i; i = E[i].nex) {
int v = E[i].v;
if (v == fa) continue;
dfs(v, u), A[++A_sz] = u;
}
}
int B[maxn << 1][maxlg2n], lg2[maxn << 1];
void init_st() {
for (int i = 1; i <= (n << 1); i++) B[i][0] = A[i];
for (int i = 2; i <= (n << 1); i++) lg2[i] = lg2[i >> 1] + 1;
for (int i = 1; i <= lg2[n << 1]; i++)
for (int j = 1; j + (1 << i) - 1 <= (n << 1); j++)
if (dep[B[i][j - 1]] < dep[B[i + (1 << (j - 1))][j - 1]])
B[i][j] = B[i][j - 1];
else B[i][j] = B[i + (1 << (j - 1))][j - 1];
}
int getlca(int u, int v) {
if (bg[u] > bg[v]) swap(u, v);
int lg = lg2[bg[v] - bg[u] + 1];
if (dep[B[bg[u]][lg]] < dep[B[bg[v] - (1 << lg) + 1][lg]])
return B[bg[u]][lg];
else return B[bg[v] - (1 << lg) + 1][lg];
}
可以发现,初始化的时间复杂度为 \(O(n\log_2 n)\),求一次 \(\rm{LCA}\) 的时间复杂度是 \(O(1)\) 的。因此总的时间复杂度是\(O(n \log_2 n + q)\) 的。