LCA的离线快速求法 - Ofnoname
source link: https://www.cnblogs.com/ofnoname/p/16179645.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
LCA的离线快速求法
最常见的LCA（树上公共祖先）都是在线算法，往往带了一个log。有一种办法是转化为“+-1最值问题”得到O(n)+O(1)的复杂度，但是原理复杂，常数大。今天介绍一种允许离线时接近线性求LCA的方法。
一个点和其他点的LCA必定是它到root路径上的所有节点之一，而另一个节点刚好在哪个节点下，LCA就是谁：
如图，标粗的箭头为当前搜索的路径，左边为已经搜索完毕的路径，右边的黑色节点尚未搜索。现在要求节点cur和节点a的LCA，显然a是什么颜色，LCA就也是这个颜色，如果a还没有被搜索到，那就不处理，把这个询问留给搜索到a的时候处理（那个时候cur肯定已经访问过了）。
那怎么做这个染色呢？我们对所有节点做一个并查集，每当一个节点搜索完毕，处理完了自己的答案，就把自己合并到父亲fa里面，那么在我搜完之后，父节点fa搜完之前，fa的其他所有儿子的公共祖先都是fa了：
当cur节点搜索完毕后，回到fa，讲cur修改为橙色并入到fa里（而且我们使用了并查集，此后查询cur的子节点也将得到fa），之后在fa搜索其他儿子节点时，他们和cur子树里的节点的LCA一定是fa，而当fa全部搜索完成后，他又被并入上级节点，以此类推，就可以在一遍dfs中就获取所有询问的答案。
参考代码：
int N, Q, p[MAX], qa[MAX], qb[MAX], ans[MAX];
vector<int> has[MAX];
struct ufs {
int in[MAX];
ufs() {
std::iota(in, in + N, 0);
}
void merge(int v, int u) { //! v合并给u
in[v] = u;
}
int find(int u) {
return in[u]==u ? u : (in[u] = find(in[u])); //! 带路径压缩
}
};
class Tree
{
std::vector<int> son[MAX];
ufs f;
void getans(int u) {
for (auto v: son[u]) {
getans(v); f.merge(v, u); //! 处理子树后，将其并入
}
for (auto i: has[u]) {
auto v (qa[i]^qb[i]^u); //! 该询问的另一个点
if (f.find(v) != v) ans[i] = f.find(v);
}
}
public:
#define root 0
Tree() {
for (int i = 1; i < N; ++i) son[p[i]].push_back(i);
getans(root);
}
#undef root
};
main() {
scanf("%d%d", &N, &Q);
for (int i = 1; i < N; ++i) scanf("%d", p + i);
for (int i = 0; i < Q; ++i) {
scanf("%d%d", qa + i, qb + i);
has[qa[i]].push_back(i);//! 把询问归到qa和qb下
has[qb[i]].push_back(i);
}
auto tr = new Tree;
for (int i = 0; i < Q; ++i)
printf("%d\n", ans[i]);
}
Recommend
-
4
好久没刷题了，复习一下：LCA。 题目很简单，就是求多叉树两个点的最近公共祖先。 链接: 洛谷 P3379 LCA（Least Common Ancestors），即最近公共祖先，是指在有根树...
-
1
Back from LCA After coming back from my somewhat extended linux.conf.au trip I spent the whole day grepping through email. Only...
-
4
FOMS/LCA Recap Finally, here's my linux.conf.au 2007 and
-
1
LCA Talk on Video I won't spare you the video of my talk about sys...
-
4
Conferences: UDS, FOMS and LCA To my surprise I have been invited to the Ubuntu Developers Summit in Mountain View early ne...
-
2
Luogu P3379 最近公共祖先 如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。 第一行包含三个正整数 N,M,SN,M,S，分别表...
-
5
随着程序越来越复杂，程序中用到的类型也越来越复杂,这种复杂性体现在两个方面。一是一些类型难于“拼写”，它们的名字既难记又容易写错，还无法明确体现其真实目的和含义。二是有时候根本搞不清到底需要的类型是什么，程序员不得不回过头去从程序的上下文中寻求帮助。...
-
3
文件的权限属性 在 linux 中，每个文件都有唯一的“所属者”（user）和“所属群组”（group）。owner 和 group 都对文件有特殊的权限 输入ls -l，就可以详细查看每个文件的权限属性。
-
9
shell 和 bash 是什么？ shell 是一种应用程序，在这个程序里输入文字指令，系统就会做出响应的操作。这个“壳程序”是我们使用系统各种功能的接口，学会了 shell 就是学会操作 linux 系统。检索/etc/shells，可以看到当前系统的 shell...
-
5
使用 ps 观察程序 ps程序可以查询当前在运行的进程信息。ps -l可以列出详细的信息，默认仅列出当前 bash 相关的进程。 sudo -ips -l
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK