최소 공통 조상 - 이진 리프팅¶
$G$가 트리라고 합시다. (u, v) 형태의 각 쿼리마다 노드 u와 v의 최소 공통 조상을 찾고자 합니다. 즉, u에서 루트 노드로 가는 경로 위에 있으면서 v에서 루트 노드로 가는 경로 위에도 있는 노드 w를 찾고자 하며, 그러한 노드가 여러 개라면 루트 노드에서 가장 멀리 떨어진 노드를 고릅니다. 다시 말해, 원하는 노드 w는 u와 v의 가장 낮은 조상입니다. 특히 u가 v의 조상이라면 u가 이 둘의 최소 공통 조상입니다.
이 글에서 설명하는 알고리즘은 트리를 전처리하는 데 $O(N \log N)$이 필요하고, 이후 각 LCA 쿼리마다 $O(\log N)$이 필요합니다.
알고리즘¶
각 노드에 대해 바로 위의 조상, 두 단계 위의 조상, 네 단계 위의 조상 등을 미리 계산해 둡니다. 이들을 배열 up에 저장합시다. 즉, up[i][j]는 노드 i에서 2^j단계 위에 있는 조상이며, 여기서 i=1...N, j=0...ceil(log(N))입니다. 이 정보를 이용하면 임의의 노드에서 그 위에 있는 임의의 조상으로 $O(\log N)$ 시간에 이동할 수 있습니다. 이 배열은 트리에 대한 DFS 순회를 이용하여 계산할 수 있습니다.
또한 각 노드에 대해 그 노드를 처음 방문한 시각(즉, DFS가 그 노드를 발견한 시각)과 그 노드를 떠난 시각(즉, 모든 자식을 방문한 뒤 DFS 함수를 빠져나온 시각)을 기록해 둡니다. 이 정보를 이용하면 한 노드가 다른 노드의 조상인지를 상수 시간에 판별할 수 있습니다.
이제 쿼리 (u, v)를 받았다고 가정합시다. 먼저 한 노드가 다른 노드의 조상인지를 바로 확인할 수 있습니다. 이 경우 그 노드가 곧 LCA입니다. u가 v의 조상이 아니고 v도 u의 조상이 아니라면, v의 조상이 아닌 노드 중 가장 높은(즉, 루트에 가장 가까운) 노드를 찾을 때까지 u의 조상들을 따라 올라갑니다(즉, x는 v의 조상이 아니지만 up[x][0]은 v의 조상인 노드 x를 찾습니다). 배열 up을 이용하면 이 노드 x를 $O(\log N)$ 시간에 찾을 수 있습니다.
이 과정을 좀 더 자세히 설명하겠습니다. L = ceil(log(N))이라고 합시다. 먼저 i = L이라고 가정합니다. up[u][i]가 v의 조상이 아니라면 u = up[u][i]로 대입하고 i를 1 감소시킵니다. up[u][i]가 조상이라면 i만 1 감소시킵니다. 음이 아닌 모든 i에 대해 이 작업을 마치고 나면 노드 u가 원하는 노드가 된다는 것은 명백합니다. 즉, u는 여전히 v의 조상이 아니지만 up[u][0]은 v의 조상입니다.
이제 LCA의 답은 명백히 up[u][0]입니다. 즉, 노드 u의 조상 중에서 v의 조상이기도 한 가장 작은 노드입니다.
따라서 LCA 쿼리에 답할 때는 i를 ceil(log(N))부터 0까지 반복하면서 각 반복마다 한 노드가 다른 노드의 조상인지를 확인합니다. 결과적으로 각 쿼리는 $O(\log N)$에 답할 수 있습니다.
구현¶
int n, l;
vector<vector<int>> adj;
int timer;
vector<int> tin, tout;
vector<vector<int>> up;
void dfs(int v, int p)
{
tin[v] = ++timer;
up[v][0] = p;
for (int i = 1; i <= l; ++i)
up[v][i] = up[up[v][i-1]][i-1];
for (int u : adj[v]) {
if (u != p)
dfs(u, v);
}
tout[v] = ++timer;
}
bool is_ancestor(int u, int v)
{
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v)
{
if (is_ancestor(u, v))
return u;
if (is_ancestor(v, u))
return v;
for (int i = l; i >= 0; --i) {
if (!is_ancestor(up[u][i], v))
u = up[u][i];
}
return up[u][0];
}
void preprocess(int root) {
tin.resize(n);
tout.resize(n);
timer = 0;
l = ceil(log2(n));
up.assign(n, vector<int>(l + 1));
dfs(root, root);
}
동적 트리에서의 이진 리프팅¶
이것은 LCA를 구하는 또 다른 방법으로, 노드 v에 리프 노드를 추가하는 연산도 지원합니다.
리프를 추가하면 그래프 전체의 진입 시각과 퇴장 시각이 바뀔 수 있으므로, 앞의 방법은 이러한 갱신을 처리하기 어렵습니다.
루트로부터 노드 u까지의 거리를 담는 배열 depth[u]를 만듭시다. 이는 트리를 DFS로 순회하여 구할 수 있습니다. 앞의 방법과 마찬가지로 배열 up[u][j]를 미리 계산합니다.
LCA 쿼리는 다음과 같이 처리합니다. 답을 구하려는 쌍을 (u, v)라고 합시다. 이제부터 depth[u] ≥ depth[v]라고 합시다(depth[v] > depth[u]이면 u와 v를 서로 바꾸면 됩니다). 이제 u를 조상 쪽으로 끌어올려 depth[u] = depth[v]가 되도록 해 봅시다. 이 조건을 만족하는 u의 조상은 정확히 depth[u]-depth[v]개의 노드만큼 위에 있습니다. 따라서 up[u][j] 테이블과 depth[u]-depth[v]의 이진 표현을 이용하여 u의 값을 해당 조상으로 바꿉시다.
이제 또 다른 문제가 남습니다. 깊이가 같은 두 정점 (u, v)의 LCA를 구하는 것입니다. 먼저 u = v인 자명한 경우를 확인합시다. 이 경우 두 값의 LCA는 u입니다. 그렇지 않다면 (u, v)의 공통 조상이 아닌 정점 중 가장 높은 정점을 찾습니다.
L=ceil(log(N))이라고 합시다. 여기서 N은 그래프가 가질 수 있는 정점의 최대 개수입니다. i = L이라고 합시다. up[u][i]=up[v][i]이면 i를 1 감소시키기만 합니다. 그렇지 않다면 u = up[u][i], v = up[v][i]로 설정한 뒤 i를 1 감소시킵니다. 이 모든 연산을 마치면 두 정점 u와 v를 얻는데, 이들은 원래 쌍의 LCA가 아니지만 up[u][0]과 up[v][0]은 LCA입니다. 이번에도 전처리 복잡도는 $O(N \log N)$이고 쿼리 복잡도는 $O( \log N)$입니다.
이 방법이 이러한 동적 환경에서 잘 동작하는 이유는 무엇입니까? 알고리즘을 수행하는 동안 필요한 것은 모든 정점에 대한 up[u][j] 배열과 각 노드의 루트로부터의 거리뿐이며, 둘 다 리프 추가 쿼리에서 $O(\log n)$ 시간에 간단히 얻을 수 있습니다.
그 대가는 쿼리 속도입니다. 앞의 방법은 조상 판정이 깊이 차이와 갈라지는 지점을 동시에 다루기 때문에 하나의 내려가는 루프로 쿼리를 처리합니다. 이 방법은 루프가 두 개 필요하고 두 번째 루프에서는 두 정점을 모두 올려야 하므로, up을 대략 세 배 더 자주 읽습니다. 정점이 $10^6$개인 트리에서 쿼리당 읽기 횟수는 22회에 비해 64회입니다.
구현¶
int n, l;
vector<vector<int>> adj;
vector<int> depth;
vector<vector<int>> up;
void dfs(int v, int p, int dist)
{
depth[v]=dist;
up[v][0] = p;
for (int i = 1; i <= l; ++i)
up[v][i] = up[up[v][i-1]][i-1];
for (int u : adj[v]) {
if (u != p)
dfs(u, v, dist+1);
}
}
int lca(int u, int v)
{
if (depth[u] < depth[v]) swap(u,v);
for (int j = l; j >= 0; --j) {
if (depth[up[u][j]] >= depth[v]) {
u = up[u][j];
}
}
if(u == v) return u;
for (int i = l; i >= 0; --i) {
if (up[u][i] != up[v][i]) {
u = up[u][i];
v = up[v][i];
}
}
return up[u][0];
}
void add_leaf(int to)
{
int v = adj.size();
adj[to].push_back(v);
adj.push_back({to});
depth.push_back(depth[to]+1);
up.push_back(vector<int>(l + 1));
up[v][0] = to;
for (int i = 1; i <= l; ++i)
up[v][i] = up[up[v][i-1]][i-1];
}
//Set max_nodes to the maximum size of the graph
void preprocess(int root, int max_nodes)
{
depth.resize(n);
l = ceil(log2(max_nodes));
up.assign(n, vector<int>(l + 1));
dfs(root, root, 0);
}
$O(n)$ 공간과 전처리 시간을 사용하는 LCA¶
이 방법을 사용하면 $O(n)$ 공간만으로 LCA를 계산할 수 있습니다. 또한 동적 트리에서도 동작하도록 확장할 수 있습니다. 이 방법은 1984년 Harel과 Tarjan이 처음 제안했습니다.
트리에서 각 노드의 깊이를 저장할 배열 depth[]를 만듭니다. 각 노드에 대해 작은 점프와 큰 점프만 정의합니다. 작은 점프는 항상 바로 위 조상을 가리킵니다(단, 루트는 자기 자신을 가리킵니다). 큰 점프는 정의가 더 복잡합니다. 노드 v에서 큰 점프를 했을 때 도달하는 노드를 big[v]로 표기합니다. big[root] = root로 둡니다.
그다음 재귀적인 정의를 만듭니다. $v$에서 하는 큰 점프의 크기를 $\ell(v) = \mathtt{depth}[v] - \mathtt{depth}[\mathtt{big}[v]]$로 쓰고, $u$의 부모를 $p$라고 합시다.
이 배열은 모든 노드에 대해 그 노드의 모든 조상의 값이 이미 계산되어 있도록 하는 순서로 계산해야 합니다. 전위 순회 순서가 이 성질을 만족하므로 여기서 사용할 수 있습니다.
이 모든 전처리를 마치고 나면 쿼리에 답하는 것은 쉽습니다. 먼저 두 노드의 깊이를 같게 맞춘 다음, 공통 조상이 아닌 가장 낮은 노드를 찾으려고 시도합니다. 이는 Dynamic LCA 알고리즘에서 했던 것과 매우 비슷하지만, 이제는 큰 점프를 할 수 있는지만 확인하고 할 수 없다면 작은 점프를 합니다. Harel과 Tarjan이 논문에서 점프를 최대 $6\lfloor{\log(d+1)}\rfloor-4$번만 사용한다는 것을 증명했으므로, 시간 복잡도는 로그 시간입니다. 공간 복잡도는 선형입니다.
여기서는 리프를 추가하는 비용이 이전 절보다 적습니다. 새 정점의 두 포인터는 그 부모만으로 결정되고 기존 정점은 전혀 바뀌지 않으므로, 삽입은 $O(1)$이며 확장해야 할 테이블도 없습니다.
구현¶
int n, l;
vector<vector<int>> adj;
vector<int> depth;
vector<int> small, big;
void dfs(int v, int p, int dist)
{
depth[v] = dist;
small[v] = p;
if(depth[p] - depth[big[p]] == depth[big[p]] - depth[big[big[p]]]){
big[v]= big[big[p]];
}
else{
big[v]=p;
}
for (int u : adj[v]) {
if (u != p)
dfs(u, v, dist+1);
}
}
int lca(int u, int v)
{
if (depth[u] < depth[v]) swap(u,v);
while(depth[u] != depth[v]) {
if (depth[big[u]] >= depth[v]) {
u = big[u];
}
else{
u = small[u];
}
}
while(u != v) {
if (big[u] != big[v]) {
u = big[u];
v = big[v];
}
else{
u = small[u];
v = small[v];
}
}
return u;
}
void add_leaf(int to)
{
int v = adj.size();
adj[to].push_back(v);
adj.push_back({to});
depth.push_back(depth[to] + 1);
small.push_back(to);
if(depth[to] - depth[big[to]] == depth[big[to]] - depth[big[big[to]]]){
big.push_back(big[big[to]]);
}
else{
big.push_back(to);
}
}
void preprocess(int root)
{
depth.resize(n);
small.resize(n);
big.resize(n);
big[root] = root;
dfs(root, root, 0);
}