joseph0528 코딩 블로그

이 문제는 설명자체는 간단한데, 트리가 주어지고 1번 쿼리는 트리의 노드를 바꾸는 거고, 2번 쿼리는 현재 만들어진 트리에서 1번 노드에서 v 노드로 가는 길에 1번 노드와 가장 가까운 검정 노드의 번호를 출력하는 문제이다. 이 문제도 여러 가지 풀이 방법이 있는 걸로 알고 있고 가장 대표적인 풀이가 HLD(Heavy heavy Light Decomposition)으로 알고 있는데, 그 풀이가 아닌 ETT(오일러 투어 테크닉) 와 lazy 세그 (느리게 갱신되는 세그먼트 트리), sparse table(희소 배열)을 이용한 풀이를 작성하겠다. 이 문제의 핵심은 2번 쿼리니 1번 쿼리는 2번쿼리의 구조 내에서 구현해 줘야 된다. 그러므로 2번 쿼리부터 설명하겠다. 1부터 v 로 가는 길에서 1에 가장 가까..