# LCA的离线快速求法

``````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]);
}
``````
原文作者：Ofnoname
原文地址: https://www.cnblogs.com/ofnoname/p/16179645.html
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。