[백준] 14268 내리 갈굼 2

내리 갈굼 2번째 문제이다

이번엔 쿼리를 날려주는데 한 노드의 상태를 출력해야한다

트리를 세그먼트 트리로 만들 수 있다면

lazy를 써서 쉽게 풀 수 있다!

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
const int MAXN = 1e5 + 5;
int p[MAXN], num[MAXN], cnum[MAXN],cnt;
bool check[MAXN];
vector<vector<int>> Graph;
int dfs(int x) {
    check[x] = true;
    int c = 0;
    for (int i = 0; i < Graph[x].size(); i++) {
        int next = Graph[x][i];
        if (!check[next]) c+=dfs(next);
    }
    num[x] = cnt++;
    cnum[x] = c;
    return c + 1;
}
void update_lazy(vector<int>&tree, vector<int>&lazy, int node, int start, int end) {
    if (lazy[node]) {
        tree[node] += (end - start + 1)*lazy[node];
        if (start != end) {
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
        lazy[node] = 0;
    }
}
void update_range(vector<int>&tree, vector<int>&lazy, int node, int start, int end, int i, int j, int val) {
    update_lazy(tree, lazy, node, start, end);
    if (i > end || j < start) return;
    if (i <= start && end <= j) {
        tree[node] += (end - start + 1)*val;
        if (start != end) {
            lazy[node * 2] += val;
            lazy[node * 2 + 1] += val;
        }
        return;
    }
    update_range(tree, lazy, node * 2, start, (start + end) / 2, i, j, val);
    update_range(tree, lazy, node * 2 + 1, (start + end) / 2 + 1, end, i, j, val);
    tree[node] = tree[node * 2] + tree[node * 2 + 1];
}
int query(vector<int>&tree, vector<int>&lazy, int node, int start, int end, int i, int j) {
    update_lazy(tree, lazy, node, start,end);
    if (i > end || j < start) return 0;
    if (i <= start && end <= j) return tree[node];
    return query(tree, lazy, node * 2, start, (start + end) / 2, i, j) + query(tree, lazy, node * 2 + 1, (start + end) / 2 + 1, end, i, j);
}
int main() {
    int n, m; scanf(" %d %d", &n, &m);
    Graph.resize(n);
    int h = (int)ceil(log2(n + 1));
    int tree_size = (1 << (h + 1));
    vector<int> tree(tree_size), lazy(tree_size);
    for (int i = 0; i < n; i++) {
        int x; scanf(" %d", &x);
        if (i == 0) continue;
        x--;
        Graph[x].push_back(i);
    }
    dfs(0);
    for (int i = 0; i < m; i++) {
        int x; scanf(" %d", &x);
        if (x == 1) {
            int pos, val; scanf(" %d %d", &pos, &val);
            pos--;
            update_range(tree, lazy, 1, 0, n - 1, num[pos] - cnum[pos], num[pos], val);
        }
        else {
            int pos; scanf(" %d", &pos);
            pos--;
            printf("%d\n", query(tree, lazy, 1, 0, n - 1, num[pos], num[pos]));
        }
    }
}