tree DP1 [알고리즘 개념] TreeDP / JAVA TreeDP Tree : cycle이 없는 그래프(서로 다른 두 노드를 잇는 간선이 1개) TreeDP는 Tree구조에서 서브트리(부분 문제)의 해를 가지고 전체 해를 구하는 방식입니다. DP에 서브트리의 어떠한 것(서브트리의 노드 개수, 서브트리의 간선 개수 등등)을 저장해둘 것이고, 보통 DFS를 통해 탐색하면서 서브트리의 해를 구해나갑니다. 정점을 기준으로 탐색해나간다면, 보통 O(N)만에 풀립니다. 백준 15681 트리와 쿼리 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ .. 2022. 3. 17. 이전 1 다음
