BOJ 16404(주식회사 승범이네)풀이

solved.ac 티어 : 플래 3

www.acmicpc.net/problem/16404

16404번: 주식회사 승범이네

이문제는 트리에 어떤 노드가 선택되었을 때 그 노드와 노드의 자식들에게 w만큼 값이 더해지는 문제다

대신 이 문제는 다른 평범한 세그먼트 트리처럼 이진트리가 아니다.

그럼 어떻게 할 수 있을까?

 

예시에 있는 입력을 가지고 트리를 만들면 이렇게 된다.(좀 이상한 건 어쩔 수 없다)

 

A부터 E까지 순서대로 1,2,3,4,5라고 할 때 A에 변화가 생기면 나머지 값들도 변화가 있어야 된다.

 

이때 dfs으로 각 정점마다 자신이 선택되었을 때의 번호와 자신의 자식 노드들을 모두 번호를 매기고 돌아왔을 때의 번호를 매겨준다.

그러면 A는 (1,5), B는 (4,4) C는 (2,2), D는 (3,4), E는 (5,5)이다.

이제 이 값들을 가지고 세그 레이지를 해주면 된다.

A에 변화가 있을 때 1부터 5까지에 변화를 주면 된다. A의 자식들은 A의 범위 안 번호 이기 때문에 자식들에게만 적용된다.

B를 선택했을 때도 B의 구간인 4부터 4까지에 값을 변경해주면 된다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> nod;
const ll N=1000000;
ll n,m;
vector<ll> graph[N];
nod Qu[N]; 
ll cnf=0,p;
vector<ll>tree(4000000);
vector<ll>tree1(4000000);
void DFS(ll v,ll p){
    Qu[v].first = ++cnf;
    for(ll nv : graph[v]){
        if (nv==p){continue;}
        DFS(nv,v);
    }
    Qu[v].second=cnf;
}
ll seg(ll n,ll s,ll e){
    if(s==e){return tree[n]=0;}
    return tree[n]=seg(n*2,s,(s+e)/2)+seg(n*2+1,(s+e)/2+1,e);
}
void propagate(ll n,ll s,ll e){
    if(tree1[n]!=0){
        if(s!=e){
            tree1[n*2]+=tree1[n];
            tree1[n*2+1]+=tree1[n];
        }
        tree[n]+=tree1[n]*(e-s+1);
        tree1[n]=0;
    }
}
ll max1(ll n,ll s,ll e,ll left,ll right){
    propagate(n,s,e);
    if(left>e||right<s){return 0;}
    if(left<=s&&e<=right){return tree[n];}
    return max1(n*2,s,(s+e)/2,left,right)+max1(n*2+1,(s+e)/2+1,e,left,right);
}
void change(ll n,ll s,ll e,ll s1,ll e1,ll f){
    propagate(n,s,e);
    if(s1<=s&&e<=e1){tree1[n]+=f;propagate(n,s,e);return;}
    if(e1<s||s1>e){return;}
    change(n*2,s,(s+e)/2,s1,e1,f);
    change(n*2+1,(s+e)/2+1,e,s1,e1,f);
    tree[n]=tree[n*2]+tree[n*2+1];
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
    cin >> n >> m;
    ll q,c,d;
    for(int i = 1; i <= n; i++){
        cin >> p;
        if(p!=-1){graph[p].push_back(i);}
    }
    DFS(1, 0);
    //for(int i=1;i<=n;i++){
    //    cout << Qu[i].first << ' ' << Qu[i].second <<'\n';
    //}
    seg(1,1,n);
    for(int i=0;i<m;i++){
        cin >> q;
        if(q==1){
            cin >> c >> d;
            change(1,1,n,Qu[c].first,Qu[c].second,d);
        }else{
            cin >> c;
            cout << max1(1,1,n,Qu[c].first,Qu[c].first) << '\n';
        }
    }
}