166. Euler Tour Technique

지금까지 수열에서 구간 업데이트와 구간 합을 구하기 위해 세그먼트 트리를 사용하였다. 이번에는 이것을 일반적인 트리 구조에 적용해 볼 것이다.

 

오일러 투어 테크닉(오일러 경로 테크닉, Euler Tour Technique, ETT)은 세그먼트 트리에서 일자형 구조에 사용한 기술을 트리 구조에 적용할 때 사용되는 방법으로 다음과 같은 쿼리들을 처리할 수 있게 해 준다. 노드마다 값을 하나씩 가진다고 하자.

• 노드 $v$에 할당된 값을 변경한다.
• 노드 $v$를 루트로 하는 서브트리의 각 노드에 할당된 값을 변경한다.
• 노드 $v$에 할당된 값을 출력한다.
• 노드 $v$를 루트로 하는 서브트리의 각 노드에 할당된 값의 합(최대, 최소 등 다양하게 변경할 수 있음)을 출력한다.

즉 노드 쿼리나 서브트리 쿼리를 처리할 수 있다. 어떤 방식으로 하는지 살펴보자.

---

먼저 트리의 노드 번호를 다시 매기는(Reordering) 과정을 거친다. 루트 노드에서 DFS를 실행하면서 방문하는 순서대로 번호를 매기면 된다.

이렇게 번호를 매겼다고 하자. 그러면 노드 쿼리와 서브트리 쿼리를 어떤 식으로 처리할 수 있는지가 눈에 들어온다. 세그먼트 트리를 사용하면 노드 쿼리는 점 쿼리와 같고 서브트리 쿼리는 구간 쿼리와 같아지는 것이다. 예를 들어 $2$번 노드를 루트로 하는 서브트리에 쿼리를 처리할 경우 느리게 갱신되는 세그먼트 트리를 이용하여 구간 $[2, 4]$에 해당 쿼리를 처리하면 된다.

 

구현은 다음과 같다. 노드 번호를 다시 매기는 부분까지만 소개한다.

#import<bits/stdc++.h>
using namespace std;
int c, r1[100005], r2[100005];
vector<int> e[100005];
void dfs(int p, int u)
{
    r1[u] = ++c;
    for(auto &v: e[u])
    {
        if(p != v)dfs(u, v);
    }
    r2[u] = c;
}
int main()
{
    int n, x, y;
    cin >> n;
    for(int i = 1; i < n; i++)
    {
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs(0, 1);
}

$v$번 노드의 번호를 $r1[v]$번으로 다시 매기고, 그 노드를 루트로 하는 서브트리가 $r1[v]$ ~ $r2[v]$번 노드로 이루어져 있게 한다.

 

이제 트리에서 노드 쿼리와 서브트리 쿼리를 처리할 수 있다. 하지만 경로 쿼리와 같은 것들은 오일러 투어 테크닉으로 처리하기 어려운 경우가 많다. 이런 쿼리들은 나중에 소개할 HLD를 이용하면 대부분 처리할 수 있다.

 

[연습문제]

 

BOJ 16404. 주식회사 승범이네 (Platinum III)

서브트리 업데이트 + 노드 확인이므로 오일러 투어 테크닉을 사용하면 문제를 해결할 수 있다.

 

CF 1062E. Company (2300)

(Todo)

 

→ solved.ac tag: euler_tour_technique