boj-2820 자동차 공장

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

2820번: 자동차 공장

우선 문제 이해가 어려웠다.

뭘 하라는건지... 한참 만에 따라 하다 억지로 이해중..

우선 range update를 팬윅트리를 이용해서 진행했다.

static void updateRange(int a, int b, int v){     update(a, v);     update(b+1, -v); }

문제는 하위 직원을 구하는 부분이 었는데.. 단순 dfs의 탐색이 아니라. 전위순회(pre-order)를 찾아야 한다.

그림으로 보면, 트리의 구조와 왼쪽과 같았다면, 각 트리의 번호를 오른쪽처럼 변경하는 것이다.

순서는 전위순회(pre-order)로 탐색하면서 번호를 붙이면 된다.

음...  reorder  젤 이해가 어려웠던 부분인데.. 위상정렬과 비슷한 형태인 것 같다.

 

 

---

import java.io.*;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class BOJ2820 {
    static int N, M, C;
    static int[] s, e, Money;
    static ArrayList<Integer>[] VT;
    static int[] PT;
    static void update (int h, int v){
        for (int i = h; i <= N ; i+=(i&-i)) PT[i]+=v;
    }
    static void updateRange(int a, int b, int v){
        update(a, v);
        update(b+1, -v);
    }
    static long query(int h){
        long result = 0;
        for (int i = h; i > 0 ; i-=(i&-i)) result += PT[i];
        return result;
    }
    static void dfs(int here){
        s[here] = ++C;
        if(VT[here]!=null){
            for (Integer next: VT[here]) {
                if(s[next]==0) dfs(next);
            }
        }
        e[here] = C;
    }
    public static void main(String[] args) throws IOException {
        System.setIn(new FileInputStream("res/input_boj_2820.txt"));
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        long Start = System.currentTimeMillis();
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        PT = new int[500001];
        s = new int[500001];
        e = new int[500001];
        Money = new int[N+1];
        C = 0;
        VT = new ArrayList[N+1];
        Money[1] = Integer.parseInt(br.readLine());
        int p, b;
        for (int i = 2; i <= N ; i++) {
            st = new StringTokenizer(br.readLine());
            p = Integer.parseInt(st.nextToken());
            b = Integer.parseInt(st.nextToken());
            Money[i] = p;
            if(VT[b]==null) VT[b] = new ArrayList<>();
            VT[b].add(i);
        }

        dfs(1);
        for (int i = 1; i <= N ; i++) {
            updateRange(s[i], s[i], Money[i]);
        }

        StringBuffer sb = new StringBuffer();
        char type;
        int a;
        for (int i = 1; i <= M ; i++) {
            st = new StringTokenizer(br.readLine());
            type = st.nextToken().charAt(0);
            if(type == 'p'){
                a = Integer.parseInt(st.nextToken());
                b = Integer.parseInt(st.nextToken());
                updateRange(s[a]+1, e[a], b);
            } else {
                a = Integer.parseInt(st.nextToken());
                sb.append(query(s[a]));
                sb.append("\n");
            }
        }
        System.out.println(sb.toString());
    }
}