LCA
【CLA】
void lca(int inl, int inr, int preRoot, int a, int b) {
if (inl > inr) return;
int inRoot = pos[pre[preRoot]], ain = pos[a], bIn = pos[b];
if (aIn < inRoot && bIn < inRoot)
lca(inl, inRoot-1, preRoot+1, a, b);
else if ((aIn < inRoot && bIn > inRoot) || (aIn > inRoot && bIn < inRoot))
printf(“LCA of %d and %d is %d.\n”, a, b, in[inRoot]);
else if (aIn > inRoot && bIn > inRoot)
lca(inRoot+1, inr, preRoot+1+(inRoot-inl), a, b);
else if (aIn == inRoot)
printf("%d is an ancestor of %d.\n", a, b);
else if (bIn == inRoot)
printf("%d is an ancestor of %d.\n", b, a);
}
int main() {
int m, n, a, b;
scanf("%d %d", &m, &n);
in.resize(n + 1), pre.resize(n + 1);
for (int i = 1; i <= n; i++) {
scanf("%d", &in[i]);
pos[in[i]] = i;
}
for (int i = 1; i <= n; i++) scanf("%d", &pre[i]);
for (int i = 0; i < m; i++) {
scanf("%d %d", &a, &b);
if (pos[a] == 0 && pos[b] == 0)
printf(“ERROR: %d and %d are not found.\n”, a, b);
else if (pos[a] == 0 || pos[b] == 0)
printf(“ERROR: %d is not found.\n”,pos[a] == 0 ? a : b);
else
lca(1, n, 1, a, b);
}
return 0;
}
文章最后发布于: 2018-12-04 17:24:10
相关阅读
LCA，最近公共祖先 博主今天回顾了倍增和Tarjan，总共用了40min码了两个模板（至少有20min在找Tarjan模板的错误，下面会讲到） LuoGu模版题
1.引入 点击转入模板题，by-luogu 2.思路 这道题目是倍增求LCA的模板题。 首先，大家都知道LCA的定义吧？（两个节点的公共父节点）如果我