BOJ)2820 자동차 공장

문제: icpc.me/2820

문제를 잘 읽어보면 1번을 루트로 가지는 트리 구조를 이룬다는걸 알 수 있다.

그럼 상사 X의 부하들은 어떻게 구분할 수 있을까? 트리 구조이기 때문에 X에서 Y로 가는 경로는 오직 하나일 것이다. 이걸 이용하여 X지점에서 시작한 DFS가 끝날 때 까지 탐색되는 모든 노드들은 X의 부하라는걸 알 수 있다.

이를 이용하여 1번 노드에서부터 DFS를 돌려 정점의 번호를 새롭게 매겨준 후 DFS가 끝나는 지점(마지막 부하)의 번호까지 알게 된다면 직원에 대한 증가연산을 구간에 대한 증가 연산으로 치환시킬 수 있다,

구간에 대한 증가 연산으로 치환을 했으니 레이지 프로퍼게이션을 이용한 세그먼트 트리나 ,펜윅 트리 등을 이용하여 쿼리를 처리해주면 된다.

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
int n, m, c, s[500001], e[500001], lazy[2000000], seg[2000000], x, y, a[500001];
vector<vector<int>> vt;
char f;
void dfs(int here) {
    s[here] = ++c;
    for (auto next : vt[here])
        if (!s[next])
            dfs(next);
    e[here] = c;
}
void u_lazy(int node, int x, int y) {
    if (!lazy[node])
        return;
    seg[node] += lazy[node] * (y - x + 1);
    if (x != y) {
        lazy[node * 2] += lazy[node];
        lazy[node * 2 + 1] += lazy[node];
    }
    lazy[node] = 0;
}
int update(int lo, int hi, int val, int node, int x, int y) {
    u_lazy(node, x, y);
    if (y < lo || hi < x)
        return seg[node];
    if (lo <= x&&y <= hi) {
        lazy[node] += val;
        u_lazy(node, x, y);
        return seg[node];
    }
    int mid = (x + y) >> 1;
    return seg[node] = update(lo, hi, val, node * 2, x, mid) + update(lo, hi, val, node * 2 + 1, mid + 1, y);
}
int query(int lo, int hi, int node, int x, int y) {
    u_lazy(node, x, y);
    if (y < lo || hi < x)
        return 0;
    if (lo <= x&&y <= hi)
        return seg[node];
    int mid = (x + y) >> 1;
    return query(lo, hi, node * 2, x, mid) + query(lo, hi, node * 2 + 1, mid + 1, y);
}
int main() {
    scanf("%d%d", &n, &m);
    vt.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        if (i != 1) {
            scanf("%d", &x);
            vt[x].push_back(i);
        }
    }
    dfs(1);
    for (int i = 1; i <= n; i++)
        update(s[i], s[i], a[i], 1, 1, n);
    for (int i = 0; i < m; i++) {
        getchar();
        scanf("%c", &f);
        if (f == 'p') {
            scanf("%d%d", &x, &y);
            if (s[x] == e[x])continue;
            update(s[x] + 1, e[x], y, 1, 1, n);
        }
        else {
            scanf("%d", &x);
            printf("%d\n", query(s[x], s[x], 1, 1, n));
        }
    }
    return 0;
}