백준 16404 - 주식회사 승범이네 [Python]

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

16404번: 주식회사 승범이네

[알고리즘 분류]

Segment Tree (with lazy propagation)

Euler Tour Technique

 

 

오일러 경로 테크닉이라는걸 배우고, 기초문제를 풀어보았다. 오일러 경로 테크닉은 루트가 있는 트리에서 어떤 정점의 서브트리에 속하는 정점들을 연속된 수로 renumbering할 수 있는 기술이다. 일단 나는 이렇게 이해했고, 이 문제는 앞서 말한 기술이 필요한 문제이다.

 

작동 순서는 정말 간단하다.

방문 순서(c)가 위 그림과 같다고 할 때, 각 정점이 담고 있는 구간은 다음과 같다.

단 한 번의 dfs로 가능하다!

 

코드는 아래와 같다. 레이지 세그 짜는 법을 까먹어서 약간 애먹었다..

import sys, math
import heapq
 
from collections import deque
from bisect import bisect_left, bisect_right
 
input = sys.stdin.readline
 
pop = heapq.heappop
push = heapq.heappush
 
 
# input
def ip(): return int(input())
def sp(): return str(input().rstrip())
 
 
def mip(): return map(int, input().split())
def msp(): return map(str, input().split().rstrip())
 
 
def lmip(): return list(map(int, input().split()))
def lmsp(): return list(map(str, input().split()))
 
############ Main! #############
 
sys.setrecursionlimit(808080)
 
L = [0 for _ in range(404040)]
R = [0 for _ in range(404040)]
g = [[] for _ in range(404040)]
seg = [0 for _ in range(404040)]
lazy = [0 for _ in range(404040)]
 
c = 0
def dfs(x, p):
    global c
    c += 1
    L[x] = c
    for i in g[x]:
        if i != p:
            dfs(i, x)
    R[x] = c
 
def lazyProp(x, s, e):
    if lazy[x] == 0:
        return
    seg[x] += (e - s + 1) * lazy[x]
    if s != e:
        lazy[x * 2] += lazy[x]
        lazy[x * 2 + 1] += lazy[x]
    lazy[x] = 0
 
def update(x, s, e, l, r, k):
    lazyProp(x, s, e)
    if e < l or r < s:
        return
    if l <= s and e <= r:
        seg[x] += (e - s + 1) * k
        if s != e:
            lazy[x * 2] += k
            lazy[x * 2 + 1] += k
        return
    m = (s + e) // 2
    update(x * 2, s, m, l, r, k)
    update(x * 2 + 1, m + 1, e, l, r, k)
    seg[x] = seg[x * 2] + seg[x * 2 + 1]
 
def getSum(x, s, e, l, r):
    lazyProp(x, s, e)
    if e < l or r < s:
        return 0
    if l <= s and e <= r:
        return seg[x]
    m = (s + e) // 2
    return getSum(x * 2, s, m, l, r) + getSum(x * 2 + 1, m + 1, e, l, r)
 
N, M = mip()
a = lmip()
for i in range(N):
    if a[i] == -1:
        continue
    g[i + 1].append(a[i])
    g[a[i]].append(i + 1)
 
dfs(1, -1)
 
for Q in range(M):
    q = lmip()
    if q[0] == 1:
        update(1, 1, N, L[q[1]], R[q[1]], q[2])
    else:
        print(getSum(1, 1, N, L[q[1]], L[q[1]]))
 
 
 
######## Praise greedev ########

이 테크닉을 사용하는 문제인지 아닌지를 모르고 풀이에 접근하는 것은 정말 어려울 것 같다.