들어가며.. 이전에 Heavy-Light Decomposition에 대해 다룬 적이 있다. 이는 트리를 몇개의 선형 배열로 바꾸는 것이며, 주로 특정한 두 정점을 잇는 경로에 포함되는 간선의 가중치나 정점에 관한 쿼리를 처리하는 데에 이용된다. 그렇다면, 해당 노드와 그 노드의 모든 자식 노드들에 관한 쿼리는 어떻게 처리할까? Euler tour technique 오일러 투어 테크닉(Euler tour technique)은 Tarjan과 Vishkin이 제안한 방법이다. 이 방법을 오일러 투어 테크닉이라고 부르는 이유는 검색 트리에서 이 테크닉을 통해 정점에 numbering 한 후, 각 간선의 역방향 간선을 만들어(자식 → 부모) numbering 한 순서대로 나열하면, 오일러 회로로 나타내지기 때문이..