Euler Tour Technique

Euler Tour Technique

오일러 투어 테크닉(Euler Tour Technique)은 서브 트리에 대한 쿼리가 주어지는 문제를 해결하기 위해 사용되는 알고리즘이다. 쿼리 예시는 다음과 같다.

노드에 가중치가 있는 트리에서 다음의 쿼리를 수행하라.
1 i v: i번 노드를 루트로 하는 서브 트리의 모든 노드에 v의 가중치를 더한다.
2 i: i번 노드의 가중치를 출력한다.

모든 노드의 초기 가중치는 0이다.

이 문제는 노드의 가중치가 갱신되면 그 노드의 모든 자식 노드들의 값도 갱신되는 형태이다. 이때 자식 노드를 업데이트 하기 위해 그래프 탐색을 한다면 매우 비효율적이다. 따라서 세그먼트 트리 같은 구간을 관리하는 자료구조를 통해 업데이트와 쿼리를 $O(\log N)$으로 해결해야 한다.

위와 같은 트리가 있다고 하자. 우선 루트노드에서 dfs를 하여 각 노드에 몇번째로 방문했는지 넘버링을 해준다. 또한 해당 노드에서의 함수가 종료되었을 때 몇번까지 dfs 넘버링이 되었는지 즉, 해당 노드를 루트로 하는 서브트리의 dfs 넘버 중 가장 큰 숫자가 무엇인지 기록한다. 아래는 그 결과이다.

In은 전자이고, Out은 후자이다. 이때 어떤 노드의 서브트리가 그 노드의 In부터 Out까지의 연속된 구간으로 표현되는 것을 확인할 수 있다.

이제 1 2 3이라는 쿼리가 들어온다면 Segment Tree에서 2번 노드의 In인 2부터 Out인 5까지의 구간에 Lazy Propagation으로 3을 더해주면 된다.

마찬가지로 2번 쿼리가 들어오면 Segment Tree에서 해당 노드의 In을 인덱스로 하는 값을 출력하면 된다.

Euler Tour Technique의 구현은 다음과 같다.

int in[100001], out[100001];

void ETT(int cur, int par){
    in[cur]=++ord; 
    for(auto i:grp[cur]) if(i!=par) ETT(i,cur); 
    out[cur]=ord; 
}

Heavy Light Decomposition

헤비 라이트 분할(Heavy Light Decomposition)은 트리에서 두 노드 사이의 단순 경로에 대한 쿼리를 해결하기 위해 사용되는 알고리즘이다. 쿼리 예시는 다음과 같다.

1 i v: i번 노드에서 부모 노드로 가는 간선의 가중치를 v로 변경한다.
2 i j: i번 노드와 j번 노드 사이의 단순 경로의 가중치 합을 출력한다.

HLD는 트리의 노드들을 heavy한 노드와 light한 노드로 분할하고 이것을 기준으로 몇 개의 체인 형태로 나누어 임의의 두 정점 사이의 경로에 최대 $\log N$개의 체인만 존재하도록 하는 자료구조이다. HLD는 쿼리를 $O((\log N)^2)$의 시간에 해결한다.

여기서 heavy한 노드란 형제 노드들(부모가 같은 노드들) 중에서 해당 노드를 루트로 하는 서브 트리의 노드의 수가 가장 많은 노드이다. 만약 하나의 부모에 그러한 노드가 여럿 존재한다면, 그 중 하나만 heavy노드로 정한다.

예시 트리에서 heavy노드를 표시한 모습이다. 이때 루트 노드는 제외한다.

루트 노드부터 dfs를 진행해서 체인을 만든다. light 노드가 한 체인의 top(가장 깊이가 작은 노드)이 되고, 해당 노드의 자식 중 heavy노드를 먼저 따라 내려가며 체인을 완성한다. 그 뒤에 나머지 자식 노드인 light노드를 새로운 체인의 top으로 하여 같은 방식으로 dfs를 반복한다. 이와 동시에 넘버링도 진행하며 편의를 위해 top의 부모로 가는 간선도 top의 체인에 포함시킨다.

이때 위 그림처럼 같은 체인에 포함된 노드들은 연속한 dfs 넘버를 갖게 된다. 따라서 체인을 기준으로 구간 쿼리를 적용할 수 있다.

우선 dfs넘버를 인덱스로하고, 해당하는 노드에서 부모 노드로 가는 간선의 가중치로 구간 합 세그먼트 트리를 만든다.

1 i v 쿼리가 들어오면 세그먼트 트리에서 인덱스가 i의 dfs 넘버인 값을 v로 업데이트 해준다.

2 i j 쿼리가 들어오면 i와 j중 포함된 체인 top의 깊이가 더 깊은것을 택하여 해당 노드부터 top까지의 구간합을 계산해 답에 더하고, top의 부모 노드로 교체하는 행위를 i와 j가 같은 체인에 속할 때까지 반복한다.

깊이가 깊은것을 택하는 이유는 두 노드가 포함된 체인의 깊이를 맞추기 위함이다. 그렇지 않으면 단순 경로를 지나쳐 루트까지 올라가버릴 수도 있다. 그 후, 두 노드가 같은 체인에 속하게 되면 마찬가지로 둘 사이의 간선의 가중치를 구간합으로 계산한 뒤 답에 더한다.

예를 들어 2 6 5라는 쿼리가 들어왔다고 하자. 검은 체인이 자주색 체인보다 top의 깊이가 깊기 때문에 정답에 검은 체인의 가중치 (5 ~ 5 구간 합)를 더해주고 i가 빨간 체인의 2번 노드(num 2)로 이동한다.

그 다음 빨간 체인보다 자주색 체인이 top의 깊이가 더 깊기 때문에 자주색 체인 top의 부모부터 5번 노드(num 7)사이 간선의 가중치 (6 ~ 7 구간 합)를 더해주고 j가 1번 노드(num 1)로 이동한다.

이제 i는 2번 노드, j가 1번 노드로 모두 빨간 체인에 속하므로 i와 j사이 간선의 가중치 (2 ~ 2 구간 합)를 더하면 끝이다.

다음은 HLD 구현으로 세그먼트 트리의 구현은 생략하였다.

void dfs1(int cur){ //heavy노드 판별을 위한 dfs
    wei[cur]=1; 
    for(auto &i:grp[cur]){
        if(i==par[cur]) continue; //부모 노드면 continue
        dep[i]=dep[cur]+1; //자식 노드 깊이 저장
        par[i]=cur; //자식 노드의 부모 저장
        dfs1(i); //자식 노드에 dfs 진행
        wei[cur]+=wei[i]; //자식 노드의 wei를 자신의 wei에 추가 
        // 가장 wei가 큰 노드(heavy ndoe)를 자식 노드 배열의 0번 인덱스로 위치 
        if(grp[cur][0]==par[cur] || wei[grp[cur][0]]<wei[i]) swap(grp[cur][0], i); 
    }
}

void dfs2(int cur){ //dfs넘버링 및 체인 생성을 위한 dfs 
    num[cur]=++ord; //dfs 넘버링 
    for(auto &i:grp[cur]){
        if(i==par[cur]) continue; 
        //자식 노드가 heavy 노드면 자신의 체인에 포함시키고 아니면 새로운 체인 생성
        top[i]=i==grp[cur][0]?top[cur]:i;  
        dfs2(i); 
    }
}

void HLD(int root){ //Heavy Light Decomposition
    dfs1(root);
    top[1]=1; 
    dfs2(root); 
}

int query(int i, int j){ //2번 쿼리 
    int res=0; 
    while(top[i]!=top[j]){ //같은 체인에 속할 때 까지
        //체인의 top의 깊이가 더 깊은 것을 i로 설정 
        if(dep[top[i]]<dep[top[j]]) swap(i, j); 
        //i가 속한 체인의 top부터 i번 노드까지의 가중치 합(세그먼트 트리 쿼리)를 반환값에 추가.
        res+=seg_sum(1,1,n,num[top[i]],num[i]); 
        i=par[top[i]]; //i를 체인 top의 부모 노드로 변경 
    }
    if(i==j) return res;
    if(num[i]>num[j]) swap(i,j); //다르다면 둘 중 넘버링이 작은 노드를 i로  
    res+=seg_sum(1,1,n,num[i],num[j]); //i노드 부터 j번 노드까지의 가중치를 더하고 리턴 
    return res;
}

Reference

공군 휴머니스트 air-wiki