ETT + Segment Tree

백준 14288번 회사문화4 문제풀이

[14288 회사 문화 4] https://www.acmicpc.net/problem/14288 .
오일러 투어 테크닉으로 트리를 배열처럼 만들고 세그먼트 트리를 이용하여 쿼리를 처리한다.

오일러 투어 테크닉을 배우면 대부분 세그먼트 트리랑 연계가 된다.
오일러 투어 테크닉은 트리를 배열 처럼 일직선으로 잘 펴는 테크닉이고 여기서 세그먼트 트리와 연계하기 쉽기 때문이다.
회사 문화 4는 14268 회사문화2와 14287 회사문화3 두 문제를 정확하게 합친 문제나 다름이 없다.
그렇다면 문제를 풀어보자,

문제상황 파악하기.

먼저 한명이 칭찬을 받으면 부하쪽으로 칭찬이 가든가 상사 쪽으로 간다.
이는 switch하는 bool형 변수 하나 만들어서 처리했다.
부하 쪽으로 가는것은 서브 트리에 전부 칭찬을 하면 되어서 쉽다.
상사쪽은 어떻게 해야할까?

Euler Tour Technique(ETT)가 뭐길래?.

위에서 잠깐 언급했듯이 트리를 잘 펴서 배열 처럼 만드는 테크닉이다.

int cnt = 0;
void dfs(int here, int parent){
    in[here] = ++cnt;
    for(int next :adj[here]){
        if(next ==parent) continue;
        dfs(next, here);
    }
    out[here] = cnt;
}

다음과 같이 루트에서 부터 dfs를 돌면서 in, out 배열에 들어가는 순서를 입력한다.
예를 들면 in[1] = 1, out[1] = 7이라면 1번 정점은 첫번째로 들어가서 7번째 턴에 나왔다는 뜻이다.
즉 2번째부터 6번째가 정점 1의 subtree가 되는 것이다.

아이디어 얻기.

부하 방향으로 칭찬 릴레이가 시작되면 쉽다. 서브트리에 전부 칭찬하면 되기 때문이다.
하지만 상사 방향은 조금 까다롭다. 구간 update를 하기에 배열에서 정확한 구간을 찾기가 쉽지 않기 때문이다.
이는 점 update + 구간 쿼리를 이용하여 해결했다.
업데이트 과정 위 그림 처럼 상사 관계가 되어있다고 치면 2번이 2만큼 칭찬받으면 2를 쓴다.
그 다음 3번이 4만큼 칭찬받으면 4를 쓴다. 또 4번이 6만큼 칭찬받으면 6을 쓴다.
그리고 2번이 칭찬 받은 양을 구하려면 2번부터 2번 이후 서브트리에 기록된 모든 수를 더한다 (2+4+6)그리고 2번 전에 기록된것을 빼면된다(0).
다시한번 예를 들어서 4번이 칭찬받은 양은 (2+4+6)-(2+4)==6이 되는 것이다.
이를 이용하여 세그먼트 트리 2개를 만든다.
1번세그는 부하방향, 2번 세그는 상사방향을 처리한다.

주의할 점

구간 update를 할때 이 아이디어를 이용하기 때문에 세그먼트 트리를 딱 배열의 크기까지만 보는게 아니라 배열의 크기 +1 만큼 봐줘야한다.

실제 코드

나머지 주의 할 점은 코드에 주석으로 처리했다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#include <cassert>
#define fast_io cin.tie(NULL); ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAX = 100001;
int n, m;
vector<int> adj[MAX];
int parent[MAX], in[MAX], out[MAX];

struct segTree{
    int tree[4*MAX];
    
    void update(int x, int val, int node, int S, int E){
        if(S==E){
            tree[node] += val;
            return;
            
        }
        int mid = (S+E)>>1;
        if(x<=mid) update(x, val, 2*node, S, mid);
        else update(x, val, 2*node+1, mid+1, E);
        tree[node] = tree[2*node] + tree[2*node+1];
    }
    
    int query(int L, int R, int node, int S, int E){
        if(R<S||L>R) return 0;
        if(L<=S&&E<=R) return tree[node];
        int mid = (S+E)>>1;
        return query(L, R, 2*node, S, mid)+query(L, R, 2*node+1, mid+1, E);
    }
};

int cnt = 0;
void dfs(int here, int parent){
    in[here] = ++cnt;
    for(int next :adj[here]){
        if(next ==parent) continue;
        dfs(next, here);
    }
    out[here] = cnt;
}

int main(){
    fast_io
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        cin >> parent[i];
        if(i!=1) adj[parent[i]].push_back(i);
    }
    dfs(1, 1);
    segTree st1, st2;
    bool sw = true;
    for(int i=0;i<m;i++){
        int o, emp; cin >> o;
        if(o==1){
            int w;
            cin >> emp >> w;
            if(sw){
                st1.update(in[emp], w, 1, 1, n+1);
                st1.update(out[emp]+1, -w, 1, 1, n+1);
            }else{
                st2.update(in[emp], w, 1, 1, n+1);
            }
        }else if(o==2){
            cin >> emp;
            cout <<st1.query(1, in[emp], 1, 1, n+1)+st2.query(1, out[emp], 1, 1, n+1)-st2.query(1, in[emp]-1, 1, 1, n+1) << '\n';
        }else{
            sw ^= 1;
        }
    }
}

ETT + Segment Tree

백준 14288번 회사문화4 문제풀이

문제상황 파악하기.

Euler Tour Technique(ETT)가 뭐길래?.

아이디어 얻기.

주의할 점

실제 코드

Leave a comment

2024

2023

2022