Codeforces DFS and Similar Tag 부수기

트리 / 그래프의 기본기인 DFS technique를 연습하려고 한다.

너무 쉬운 건 말고, Div.1 A ~ B  부터 짬짬이 풀어야지.

링크

396C. On Changing Tree

코드

트리에 기본적으로 DFS numbering을 해주자.

잘 모르겠다면 코드, 또는 다음 설명을 참조.

노드 \(v\)가 발견되는 시점을 \(dt[v]\), 노드 \(v\)의 탐색이 끝나는 시점을 \(ft[v]\), 노드 \(v\)의 깊이를 \(dep[v]\)라고 한다.

합 세그먼트 트리를 2개 관리한다. 각각 \(X, K\)라고 하자.

type 1 쿼리 \((v,x,k)\) :

\(X\)의 \([dt[v], ft[v]]\)에 \(x + k \cdot dep[v]\)를 더해줌.

\(K\)의 \([dt[v], ft[v]]\)에 \(k\)를 더해줌.

type 2 쿼리 \((v)\) :

\(X(dt[v]) - K(dt[v]) \cdot dep[v]\)를 출력하면 됨.

왜 되는지는 직접 노트에 써보면 알 수 있다. 핵심은 \(k \cdot dep[v]\)항을 \(X\)에 몰아주는 관찰.