오일러 경로 테크닉

다음과 같은 트리가 있다고 가정해보자. 1번 정점이 루트이고, DFS 방문 순서대로 번호가 붙여져있다.

이 트리를 배열에 저장하면 각 정점을 루트로 하는 서브트리를 구간으로 나타낼 수 있게 된다. (번호가 DFS 방문 순서대로 되어있어야 성립한다. 일반적인 트리가 주어지는 경우 구간을 계산하기 위한 번호를 다시 붙여야 한다.)

구간의 시작지점은 각 정점이 처음 방문 되었을 때, 끝 지점은 그 정점에서의 DFS함수가 끝났을 때의 번호를 저장함으로써 알 수 있다.

이것을 이용하는 것이 오일러 경로 테크닉이다.

오일러 경로 테크닉을 활용하는 대표적인 문제로 회사 문화 2,3,4가 있다.

회사 문화 2

https://www.acmicpc.net/problem/14268

영선회사에는 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하의 모든 부하들이 칭찬을 받는다. 모든 칭찬에는 칭찬의 정도를 의미하는 수치가 있는데, 이 수치 또한 부하들에게 똑같이 칭찬 받는다.

이때 i번째 직원이 직속 상사로부터 w만큼 칭찬받거나 i번쨰 직원이 칭찬받은 정도를 출력하는 쿼리가 여러개 주어지면 각 쿼리에 대해 계산하거나 출력하는 문제이다.

세그먼트 트리를 활용하여 i번째 직원이 w만큼 칭찬받으면 i번째 직원의 서브트리 구간에 값을 더해준다. 그리고 조회할 때는 i번쨰 직원의 서브트리의 루트, 즉 구간의 첫번째 지점을 조회하면 된다.

#include <iostream>
#include <algorithm>
#include <vector>
#define MAX 100001
using namespace std;

long long tree[MAX*4];
long long lazy[MAX*4];
pair<int, int> range[MAX];

// (세그먼트 트리)

int cnt=0;
vector<int> V[MAX];
void dfs(int x) {
    range[x].first=++cnt;
    for (int i=0;i<V[x].size();i++) {
        dfs(V[x][i]);
    }
    range[x].second=cnt;
}

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int n,m;
    cin>>n>>m;
    for (int i=1;i<=n;i++) {
        int a;
        cin>>a;
        V[a].push_back(i);
    }
    cnt=0;
    dfs(1);

    while (m--) {
        int t;
        cin>>t;
        if (t==1) {
            int a,b;
            cin>>a>>b;
            update_tree(1, n, 1, range[a].first, range[a].second, b);
        } else if (t==2) {
            int a;
            cin>>a;
            cout<<sum_tree(1, n, 1, range[a].first, range[a].first)<<"\n";
        }
    }
}

회사 문화 3

https://www.acmicpc.net/problem/14287

회사 문화 3은 회사 문화 2에서 반댓방향으로 칭찬이 진행되는 문제이다. 상사가 아래에 있는 부하를 칭찬하는게 아니라, 부하가 상사를 칭찬하면 그 위로 쭉 사장까지 모두 칭찬을 받는다.

세그먼트 트리를 활용하여 i번째 직원이 w만큼 칭찬받으면 구간의 첫번째 지점에 값을 더하고, 그리고 조회할 때는 i번째 직원의 서브트리 구간의 합을 구하면 된다.

    // ...
    while (m--) {
        int t;
        cin>>t;
        if (t==1) {
            int a,b;
            cin>>a>>b;
            update_tree(1, n, 1, range[a].first, range[a].first, b);
        } else if (t==2) {
            int a;
            cin>>a;
            cout<<sum_tree(1, n, 1, range[a].first, range[a].second)<<"\n";
        }
    }

회사 문화 4

https://www.acmicpc.net/problem/14288

부하 방향의 내리칭찬과 상사 방향의 내리칭찬이 섞이며 주어지는 문제이다. 각 방향의 내리칭찬이 서로 연관이 없으므로, 트리를 2개 사용하여 각각 계산하고 더해주도록 구현하면 된다.

    // ...
    while (m--) {
        int t;
        cin>>t;
        if (t==1) {
            int a,b;
            cin>>a>>b;
            if (flag) update_tree(f_tree, f_lazy, 1, n, 1, range[a].first, range[a].second, b);
            else update_tree(r_tree, r_lazy, 1, n, 1, range[a].first, range[a].first, b);
        } else if (t==2) {
            int a;
            cin>>a;
            cout<<sum_tree(f_tree, f_lazy, 1, n, 1, range[a].first, range[a].first) +
                sum_tree(r_tree, r_lazy, 1, n, 1, range[a].first, range[a].second)<<"\n";
        } else if (t==3) {
            flag=!flag;
        }
    }