링크 컷 트리를 모른다면 먼저 아래 글(또는 유사한 설명글)을 읽고 와 주세요.
https://justicehui.github.io/hard-algorithm/2021/01/01/link-cut-tree/
시험기간을 맞아 PS를 다시 시작하면서 트리와 쿼리 13(:ruby1:)을 먹으려고 시도하고 있었습니다. 문제를 요약하면, 정점에 가중치가 부여된 트리가 주어질 때
쿼리를 처리하면 됩니다.
이는 탑 트리로 처리할 수 있음이 잘 알려져 있습니다. 그래서 탑 트리를 공부하려고 시도했으나, 전혀 이해가 되지 않았습니다. 그런데 문제 태그에 링크 컷 트리가 있는 것을 보고 “링컷으로는 서브트리 쿼리를 처리할 수 없는 거 아니었나?”라는 생각에 검색을 해 보았고, 이런 글을 찾았습니다.
https://infossm.github.io/blog/2025/08/26/Link-Cut-Tree-Subtree-Query/
링크 컷 트리로 서브트리 add 또는 set 쿼리를 처리하며 sum, max, min 값을 관리하는 방법을 담은 글입니다. 이 지식을 가지고 구현을 시도했으나, 실패했습니다.
멀티셋과 네 개의 레이지를 함께 관리해주는 것이 매우 어려워서 포기했는데, 나중에 보니 jthis님 구현에는 멀티셋이 없더라고요..
그리고 대부분의 글에서 중국인들이 ‘AAA Tree’라는 것을 웰논이라 주장하는 것을 보았습니다. 그래서 그 코드를 보고 이해한 후, AAA Tree를 설명하는 글을 작성하게 되었습니다.
추가) AAA Tree와 거의 같은 원리의 자료 구조를 설명하는 영어 블로그들을 찾았습니다. https://mzhang2021.github.io/cp-blog/ds5/ https://codeforces.com/blog/entry/103726 AAA보다는 느리(ㄹ 것으로 추정되)지만, 관심이 있다면 읽어보는 것도 나쁘지 않을 것 같아요.