[백준/14287] 회사 문화 3 (Python)

Problem : https://www.acmicpc.net/problem/14287

14287번: 회사 문화 3

 

Difficulty : Platinum 3

 

Status : Solved

 

Time : 00:14:11

 

---

 

문제 설명

 

 

영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하의 모든 부하들이 칭찬을 받는다.

이러한 내리 칭찬은 회사에 가장 큰 장점이 되었고, 사장 영선이는 이 장점을 이용하기 위하여 단 하루만 반대로 하기로 했다. 즉, 부하가 상사를 칭찬하면, 그 위로 쭉 사장까지 모두 칭찬을 받는다.

칭찬에 대한 정보는 실시간으로 주어진다.

입력으로 아래와 같은 쿼리가 주어질 것이다.

 

1 i w: i번째 직원이 직속 부하 중 한 명으로부터 w만큼 칭찬을 받는다. (1 ≤ i ≤ n, 1 ≤ w ≤ 1,000) 부하가 없다면 입력으로 들어오지 않는다.
2 i: i번째 직원이 칭찬을 받은 정도를 출력한다. (1 ≤ i ≤ n)

 

직속 상사와 직속 부하관계에 대해 주어지고, 쿼리가 주어졌을 때 2번 쿼리에 따라 출력하시오.

 

 

입력 및 출력

 

입력

 

첫째 줄에는 회사의 직원 수 n명, 쿼리의 개수 m이 주어진다. 직원은 1번부터 n번까지 번호가 매겨져 있다. (2 ≤ n, m ≤ 100,000)

둘째 줄에는 직원 n명의 직속 상사의 번호가 주어진다. 직속 상사의 번호는 자신의 번호보다 작으며, 최종적으로 1번이 사장이다. 1번의 경우, 상사가 없으므로 -1이 입력된다.

다음 m줄에는 쿼리가 한 줄에 하나씩 주어진다.

 

출력

 

2번 쿼리가 주어질 때마다, 알맞게 출력하시오.

 

입력 예시

 

5 6
-1 1 2 3 4
1 2 2
1 3 4
1 4 6
2 5
2 3
2 1

 

출력 예시

 

0
10
12

 

 

---

 

풀이

 

오일러 경로 테크닉 + 세그먼트 트리 문제. 상향식 전파를 사용하는 문제를 복습할 겸 도전하였다.

 

2023.12.31 - [PS/백준] - [백준/18227] 성대나라의 물탱크 (Python)

[백준/18227] 성대나라의 물탱크 (Python)

 

불균형한 트리 형태를 오일러 경로 테크닉을 이용해 밸런스된 세그먼트 트리로 바꾸고, 이를 상향식으로 업데이트 및 출력하는 트릭이 핵심이다.

 

• 갱신 쿼리 : 현재 직원 i에 해당하는 노드만을 업데이트한다. 이 i의 상사들은 세그먼트 트리의 업데이트 과정에서 같은 값이 더해진다.
• 출력 쿼리 : 해당하는 직원 i 및 i의 모든 직속 직원들에 대한 합을 출력한다. 이 값은 오일러 경로 테크닉에 의해 index[i][0], index[i][1]의 범위로 나타내어진다.

 

풀이 코드

from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)
N, M = map(int, input().split())
children = defaultdict(list)
for i, p in enumerate(map(int, input().split())) :
  children[p-1].append(i)

index = [[0]*2 for _ in range(N)]
tree = [0]*(4*N)
idx = 0
def dfs(node) :
  global idx
  index[node][0] = idx
  for child in children[node] :
    idx += 1
    dfs(child)
  index[node][1] = idx

def update(target, value) :
  start, end, idx = 0, N-1, 1
  while start < end :
    tree[idx] += value
    mid = (start + end) // 2
    if target <= mid :
      end = mid
      idx = idx*2
    else :
      start = mid+1
      idx = idx*2+1
  tree[idx] += value

def search(left, right, start=0, end=N-1, idx=1) :
  if end < left or start > right :
    return 0
  if left <= start <= end <= right :
    return tree[idx]
  mid = (start + end) // 2
  lval = search(left, right, start, mid, idx*2)
  rval = search(left, right, mid+1, end, idx*2+1)
  return lval + rval

dfs(0)
for _ in range(M) :
  q, *cmd = map(int, input().split())
  if q == 1 :
    i, val = cmd
    update(index[i-1][0], val)
  else :
    i = cmd[0]
    print(search(index[i-1][0], index[i-1][1]))

풀이 완료!