(14268) 회사 문화 2

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

단계별로 풀어보기

52단계(세그먼트 트리 2) 1번째

 

 

 

트리에서 갱신 쿼리가 주어진 입력에 해당하는 노드의 모든 자식에 적용되는 경우 등에는 오일러 경로 테크닉을 쓸 수 있다. 이를 통해 일반적인 트리를 새그먼트 트리로 변환할 수 있다. 전위 순회는 노드를 먼저 방문한 뒤 자식(서브트리)을 방문하고 후위 순회는 먼저 자식을 방문한 뒤 노드를 방문하므로, 각 노드에 대해 [전위 순회한 순서, 후위 순회한 순서] 구간은 해당 노드를 루트로 하는 서브트리가 된다. 갱신이 구간 단위로 이루어지므로 느리게 갱신되는 세그먼트 트리를 쓰거나 이 문제처럼 구간을 단일 노드 업데이트로 바꾸는 테크닉(가능하다면)을 써야 한다.

주의할 점으로 트리에 초기 값이 있는 경우 처음 세그먼트 트리를 구성할 때 트리의 정점 번호를 그대로 세그먼트 트리의 번호에 매칭하면 안 되고 전위 순회한 순서로 만들어진 새로운 인덱스를 기준으로 매칭시켜야 한다.

 

 

 

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m, cnt;
  
  cin >> n >> m >> cnt; // cnt는 사장 상사 입력 -1 처리용
  
  vector<int> in(n+1), out(n+1);
  vector<vector<int>> adj(n+1);
  
  for(int i=2;i<=n;i++){
    int x;
    
    cin >> x;
    
    adj[x].push_back(i);
  }
  
  auto dfs= [&](auto self, int now, int prev) -> void {
    in[now]= ++cnt;
    
    for(int next:adj[now]){
      if(next==prev)  continue;
      
      self(self, next, now);
    }
    
    out[now]= cnt;
  };
  
  cnt= 0;
  dfs(dfs, 1, 0);
  
  int treesize= (1<<(((int)ceil(log2(n)))+1));
  vector<long> v(n+1), segtree(treesize);
  
  auto update= [&](auto self, int s, int e, int node, int idx, long val) -> void {
    if(idx<s||e<idx)  return;
    
    if(s==e){
      segtree[node]+= val;
    }else{
      self(self, s, s+(e-s)/2, node*2, idx, val);
      self(self, s+(e-s)/2+1, e, node*2+1, idx, val);
      segtree[node]= segtree[node*2]+segtree[node*2+1];
    }
  };
  
  auto query= [&](auto self, int s, int e, int node, int l, int r) -> long {
    if(r<s||e<l)  return 0;
    
    if(l<=s&&e<=r){
      return segtree[node];
    }else{
      long lsum= self(self, s, s+(e-s)/2, node*2, l, r);
      long rsum= self(self, s+(e-s)/2+1, e, node*2+1, l, r);
      return lsum+rsum;
    }
  };
  
  while(m--){
    int q;
    
    cin >> q;
    
    if(q==1){
      int i, w;
      
      cin >> i >> w;
      
      update(update, 1, n, 1, in[i], w);
      if(out[i]+1<=n)  update(update, 1, n, 1, out[i]+1, -w);
    }else{
      int i;
      
      cin >> i;
      
      cout << query(query, 1, n, 1, 1, in[i]) << "\n";
    }
  }
  
  return 0;
}