트리에 임의로 번호를 할당해보세요.

번호를 할당하는 방법을 (부모노드 < 자식노드) 를 항상 유지하도록

트리 순회를 이용해서 번호를 할당해보세요.

그러면 트리를 펼치는 효과를 얻을 수 있을거에요.

보통 세그먼트 트리 문제에서 a 부터 b까지 값 x를 더하는 쿼리를 주어주는 형태인데

이게 트리로 주어져서 다른 방법으로 풀 수도 있는데

문제 특성을 이용하고, 트리에 임의로 번호를 주면 일반적인 세그먼트 + lazy propagation문제로

다시 재정의할 수 있을 거에요~

트리를 전위순회를 하면 방문 순서에 따라 노드 번호를 다시 매길 수 있습니다.

그러면 순회를 할 때 각 노드에 도달한 시점과, 그 노드의 탐색을 끝내고 나가는 시점 사이에 방문한 노드들은, 그 노드를 루트로 하는 서브트리의 노드들이 되므로, 다시 매겨진 노드 번호의 어떤 구간으로 표현을 할 수 있게 됩니다. 이를 이용하면 '어떤 노드를 루트로 하는 서브트리에 대한 연산'은 '그 노드를 방문한 시점과 떠나는 시점 사이의 노드들'에 대한 연산으로 변환이 됩니다. 이렇게 노드 번호를 방문 순서에 따라 다시 매기는 것을 '일렬로 편다'고 표현하는 것이고, 일차원으로 표현이 되기 때문에 세그먼트 트리 같은 자료구조도 쓸 수 있게 됩니다.

아 ㅠㅠㅠㅠ두분 덕분에 이해됐습니다.  공부해볼 수 있겠네요

정말 감사드립니다!!!