이 블로그의 "트리에 관하여" 시리즈의 첫 번째 카테고리, ❮Tree DP❯에서 다루는 첫 번째 주제이다. 이 테크닉은 다른 이름으로도 알려져 있다. KOI에 출제된 어떤 유명한 문제의 이름을 딴 것인데, 스포일러가 될 수 있으므로 연습 문제 목차에서 후술 하겠다. Square-order tree DP? 사실 이건 그 자체로 뭔가 해야 하는 테크닉은 아니다. 트리 DP 점화식이 2차원으로 나오고, 전이 과정을 합쳐서 대충 보기에는 $O(n^3)$의 시간 복잡도를 가져야 할 것으로 보이는 후술 할 조건을 만족하는 알고리즘이 사실 $O(n^2)$이라는 더 좋은 시간 복잡도를 갖는다는 사실을 이용하는 테크닉이다. 만족해야 하는 조건은 구한 점화식 $\text{dp}(x,y)$에 대해, $x$가 각 노드를 뜻하..