[백준 18227번] [세그먼트 트리 / 오일러 투어 테크닉] 성대나라의 물탱크

Approach

자기보다 아래에 있는 트리에 물이 채워지면 현재 자신이 위치한 트리의 높이만큼의 물이 채워지는 방식이다.

따라서, 해당 위치에 얼마나 물이 채워져있는지는 자기 자신을 루트 노트로 가지는 subtree안에 속한 구간할을 구하면 된다.

 

따라서 트리의 구간합을 구하는 방식이므로 오일러 투어 테크닉(ETT)를 생각해주면 된다.

따라서 노드 i안에 있는 물의 양은 다음과 같다. $$query[dfs\_in[i], dfs\_out[i]] * depth[i]$$

 

이해가 안된다면 다음 블로그 글을 참고하도록 하자.

https://thekeykim.github.io/posts/BOJ_18227/

[백준] 18227 - 성대나라의 물탱크 C++

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)

using namespace std;
typedef long long ll;

int dfs_in[200001];
int dfs_out[200001];
int tree_depth[200001];
int visited[200001];
vector<int> edge[200001];
ll seg[800004];

int EulerTour(int index, int count, int depth){
    visited[index] = 1;
    dfs_in[index] = count;
    tree_depth[index] = depth;
    for(int i = 0; i < edge[index].size(); i++){
        int v = edge[index][i];
        if(visited[v] == 0) count = EulerTour(v, ++count, depth + 1);
    }
    dfs_out[index] = count;
    return count;
}

void update(int node_index, int node_left, int node_right, int index){
    if(index < node_left || node_right < index) return;
    seg[node_index] += 1;
    if(node_left == node_right) return;
    int mid = (node_left + node_right) / 2;
    update(node_index * 2, node_left, mid, index);
    update(node_index * 2 + 1, mid + 1, node_right, index);
    return;
}

ll query(int node_index, int node_left, int node_right, int query_left, int query_right){
    if(query_right < node_left || node_right < query_left) return 0;
    if(query_left <= node_left && node_right <= query_right) return seg[node_index];
    int mid = (node_left + node_right) / 2;
    return query(node_index * 2, node_left, mid, query_left, query_right) +
           query(node_index * 2 + 1, mid + 1, node_right, query_left, query_right);
}

int main(void){
    fastio;
    memset(visited, 0, sizeof(visited));
    memset(seg, 0, sizeof(seg));
    memset(tree_depth, 0, sizeof(tree_depth));
    int n, c;
    cin >> n >> c;

    for(int i = 1; i < n; i++){
        int a, b;
        cin >> a >> b;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }

    EulerTour(c, 1, 1);
    
    int q;
    cin >> q;

    for(int i = 0; i < q; i++){
        int a, b;
        cin >> a >> b;
        if(a == 1){
            update(1, 1, n, dfs_in[b]);
        }
        else{
            cout << query(1, 1, n, dfs_in[b], dfs_out[b]) * tree_depth[b] << "\n";
        }
    }
    return 0;
}