오일러 투어 테크닉

아이디어!

• 트리에서 어떤 정점이 존재할 때 이 정점을 구간에 대해서 표현하고 싶을 때 오일러 투어 테크닉을 사용한다.

예를 들어 위와 같은 그림이 있다고 하자!

여기에서 2번 정점을 살펴보면 2번은 3,4,5의 정점을 포함하고 있음을 확인할 수 있다.

즉 우리는 오일러 투어 테크닉을 활용한다면 시작점은 2로 표시해주고 끝점을 5로 지정하여서 정점을 구간에 대해서 표현할 수 있다!

1번 정점과 같은 경우에도 시작점은 1이고 끝점을 5로 하여서 구간에 대해서 표현할 수 있다.

적용!

• dfs를 활용하면 깊이를 우선으로 탐색하기 때문에 각 정점의 범위를 기록하기 유용하다!
• 트리의 루트에서 dfs를 시작하여서 각 노드를 처음 방문할 때, 그리고 다시 돌아올 때를 기록해 준다.
• 오일러 투어 테크닉을 구현할 때는 출발과 끝을 기록해 줄 배열 두 개가 필요하다.
• 알고리즘을 코드에 적용해 본다면 다음과 같다.

//BOJ 2820 자동차 공장

#include<bits/stdc++.h>
#define INF 500004
using namespace std;
int n, m, cnt;

vector<int> v[INF];
long long cost[INF], t[INF * 4], lazy[INF * 4];
int s[INF], e[INF];

void propagation(int node, int l, int r) {
    if (lazy[node]) {
        t[node] += lazy[node] * (r - l + 1);
        if (l != r) {
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
        lazy[node] = 0;
    }
}

void update(int node, int l, int r, int x, int y, int val) {
    propagation(node, l, r);
    if (y < l || r < x) return;
    if (x <= l && r <= y) {
        lazy[node] += val;
        propagation(node, l, r);
        return;
    }
    int middle = (l + r) / 2;
    update(node * 2, l, middle, x, y, val);
    update(node * 2 + 1, middle + 1, r, x, y, val);
    t[node] = t[node * 2] + t[node * 2 + 1];
}

long long query(int node, int l, int r, int idx) {
    propagation(node, l, r);
    if (l == r) return t[node];
    int middle = (l + r) / 2;
    if (idx <= middle) return query(node * 2, l, middle, idx);
    else return query(node * 2 + 1, middle + 1, r, idx);
}

void find_boss(int idx) { //오일러 경로 테크닉
    s[idx] = ++cnt;
    for (int i : v[idx]) find_boss(i);
    e[idx] = cnt;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        int boss;
        if (i == 1) cin >> cost[i];
        else {
            cin >> cost[i] >> boss;
            v[boss].push_back(i);
        }
    }

    find_boss(1);

    for (int i = 1; i <= n; i++) update(1, 1, n, s[i], s[i], cost[i]);

    for (int i = 1; i <= m; i++) {
        char c;
        cin >> c;

        if (c == 'p') {
            int x, y;
            cin >> x >> y;
            update(1, 1, n, s[x] + 1, e[x], y);
        } else {
            int x;
            cin >> x;
            cout << query(1, 1, n, s[x]) << "\n";
        }
    }
}

• 이 코드는 오일러 테크닉 투어를 통해서 구간을 구한 다음에 각 구간에 대해서 업데이트를 하거나 쿼리를 구하는 방식으로 작동하는 코드이다. 
• 여기에서 오일러 투어 테크닉 부분을 확인해 본다면 다음과 같다.

void find_boss(int idx) { //오일러 경로 테크닉
    s[idx] = ++cnt;
    for (int i : v[idx]) find_boss(i);
    e[idx] = cnt;
}

• 특정한 정점에서 자신을 포함한 하위 정점을 구하는 데 활용할 수 있다.
• dfs를 활용한다면 자신의 부하 정점을 모두 방문한 다음에 현제의 정점으로 돌아오게 되면서 범위를 확인할 수 있게 된다.

cf)
하지만 양방향 간선으로 주어지게 된다면 위의 코드에 중복 반복을 방지하기 위해서 parent변수를 추가해 준다!

void find_boss(int idx, int parent) { //오일러 경로 테크닉
    s[idx] = ++cnt;
    for (int i : v[idx]) {
          if(i!=parent) find_boss(i, x);
    }
    e[idx] = cnt;
}​