BOJ)14288 내리 갈굼4

문제:icpc.me/14288

트리에서 질의를 처리하는 문제이다.

우선 dfs를 이용하여 트리의 번호를 reordering 시켜주어 트리를 구간으로 생각해보자.

문제를 풀기 위해서 일반의 경우와 야자의 경우에 업데이트 시켜주는 영역을 다르게 생각해보자

일반의 경우만 생각해본다면 value가 아래로 전파되기 때문에 나의 자식들의 구간에 업데이트 시켜준 뒤, 답을 가져올 때는 해당 지점의 값을 출력하면 될것이다.

야자의 경우에는 value가 위로 전파되므로 나의 위치에 업데이트 시킨 뒤, 답을 가져올 때, 내 자식들의 업데이트 현황을 다 더해주면 되므로, 자식들의 구간의 합을 출력하면 될것이다.

두가지 모두 Fenwick tree를 이용하여 구현 가능하므로 2개의 fenwick tree를 구현하면 문제를 해결할 수 있다.

lazy propagation을 이용한 seg tree로도 문제를 해결할 수 있다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n,m,x,y,z,st[100010],ed[100010],tree[100010],c,tree2[100010],f;
vector<vector<int>> vt;
void upd(int x,int val,int *t){
    for(int i=x;i<=n;i+=i&-i)
        t[i]+=val;
}
int query(int x,int *t){
    int ret=0;
    for(int i=x;i>0;i-=i&-i)
        ret+=t[i];
    return ret;
}
void upd(int x,int y,int val,int *t){
    upd(x,val,t),upd(y+1,-val,t);
}
int dfs(int here){
    ed[here]=st[here]=++c;
    for(auto next:vt[here])
        ed[here]=max(dfs(next),ed[here]);
    return ed[here];
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    vt.resize(n+1);
    for(int i=1;i<=n;i++){
        cin>>x;
        if(i!=1)vt[x].push_back(i);
    }
    dfs(1);
    for(int i=0;i<m;i++){
        cin>>x;
        if(x==1){
            cin>>y>>z;
            if(f)
                upd(st[y],z,tree);
            else
                upd(st[y],ed[y],z,tree2);
        }
        else if(x==3)
            f^=1;
        else{
            cin>>y;
            cout<<query(ed[y],tree)-query(st[y]-1,tree)+query(st[y],tree2)<<"\n";
        }
    }
    return 0;
}