luogu P3379 【模板】最近公共祖先（LCA）
Description--Input--Output--Sample Input--Sample Output--说明--解题思路--代码--
Description–
给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。
Input–
第一行包含三个正整数 N,M,SN,M,S，分别表示树的结点个数、询问的个数和树根结点的序号。
接下来 N-1N−1 行每行包含两个正整数 x, yx,y，表示 xx 结点和 yy 结点之间有一条直接连接的边（数据保证可以构成树）。
接下来 MM 行每行包含两个正整数 a, ba,b，表示询问 aa 结点和 bb 结点的最近公共祖先。
Output–
输出包含 MM 行，每行包含一个正整数，依次为每一个询问的结果。
Sample Input–
5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5
Sample Output–
4
4
1
4
4
说明–
对于 30%30% 的数据，N\leq 10N≤10，M\leq 10M≤10。
对于 70%70% 的数据，N\leq 10000N≤10000，M\leq 10000M≤10000。
对于 100%100% 的数据，N\leq 500000N≤500000，M\leq 500000M≤500000。
样例说明：
该树结构如下： 第一次询问：2, 42,4 的最近公共祖先，故为 44。
第二次询问：3, 23,2 的最近公共祖先，故为 44。
第三次询问：3, 53,5 的最近公共祖先，故为 11。
第四次询问：1, 21,2 的最近公共祖先，故为 44。
第五次询问：4, 54,5 的最近公共祖先，故为 44。
故输出依次为 4, 4, 1, 4, 44,4,1,4,4。
解题思路–
LCA（Least Common Ancestors），即最近公共祖先，是指在有根树中，找出某两个结点u和v最近的公共祖先。 ———来自百度百科
我们先考虑一个一个往上跳，嗯，肯定会T 然后，请出我们的倍增，也就是跳 1,2,4,8,16,32 … 但是在这里我们要反着跳（不然会跳过，跳到了祖先而不是他们的lca），也就是按32,16,8,4,2,1…跳，（跳到lca的儿子那里） 这样，向上跳的次数就会大大减小，时间复杂度为O(nlogn)
终于腾出时间打lca了（TAT），我知道我很菜所以请巨爷们别老是说我了好吧。。。
代码–
#include <iostream>
#include <cstdio>
using namespace std
;
int n
, m
, s
, a
, b
, t
;
int lg
[500005], ls
[500005], dep
[500005], fa
[500005][55];
struct ooo
{
int x
, next
;
}f
[1000005];
void dfs(int xx
, int father
)
{
fa
[xx
][0] = father
;
dep
[xx
] = dep
[father
] + 1;
for (int i
= 1; i
<= lg
[dep
[xx
]]; ++i
)
fa
[xx
][i
] = fa
[fa
[xx
][i
- 1]][i
- 1];
for (int i
= ls
[xx
]; i
; i
= f
[i
].next
)
if (f
[i
].x
!= father
)
dfs(f
[i
].x
, xx
);
}
int lca(int xx
, int yy
)
{
if (dep
[xx
] < dep
[yy
])
swap(xx
, yy
);
while (dep
[xx
] > dep
[yy
])
xx
= fa
[xx
][lg
[dep
[xx
] - dep
[yy
]] - 1];
if (xx
== yy
)
return xx
;
for (int i
= lg
[dep
[xx
]] - 1; i
>= 0; --i
)
if (fa
[xx
][i
] != fa
[yy
][i
])
xx
= fa
[xx
][i
], yy
= fa
[yy
][i
];
return fa
[xx
][0];
}
int main()
{
scanf("%d%d%d", &n
, &m
, &s
);
for (int i
= 1; i
< n
; ++i
)
{
scanf("%d%d", &a
, &b
);
f
[++t
] = (ooo
) {b
, ls
[a
]}, ls
[a
] = t
;
f
[++t
] = (ooo
) {a
, ls
[b
]}, ls
[b
] = t
;
}
for (int i
= 1; i
<= n
; ++i
)
lg
[i
] = lg
[i
- 1] + (1 << lg
[i
- 1] == i
);
dfs(s
, 0);
for (int i
= 1; i
<= m
; ++i
)
{
scanf("%d%d", &a
, &b
);
printf("%d\n", lca(a
, b
));
}
return 0;
}
