tree dp1 [코드트리] 4 - 트리 DP, LCA, 한 달 공부 후기, 2차 갭체크 트리 DP트리dp -> 트리 DP는 여러 서브트리의 최적해의 조합으로 이루어진다.반환값이 있는 DFS는 최상위 루트 노드에서 값을 한번만 처리할 때, dp 배열을 대신해서 쓸 수 있고 점화식의 정의를 dfs 구현으로 대체할 수 있다. 상태를 설계할때는 현재 노드 u가 부모 노드에게 어떤 값을 넘겨줘야 하는지를 u의 입장에서 생각해봐야 함.-> 현재 노드가 부모에게 어떤 약속을 하는가?-> u 기준으로 u가 누구에 의해 해결되는가? LCALCA -> Lowest Common Ancestor, 가장 가까운 공통 조상 구하기트리에서는 특정 정점에서 특정 정점으로 가는 경로가 유일하다. 이 성질을 활용해서 가장 가까운 공통 조상을 구하기 위한 전처리를 미리 구해놓고 쿼리마다 적절히 연산하면쿼리수가 많아도 N+Q.. 2026. 6. 3. 이전 1 다음
