1. 문제  2. 풀이 방법문제를 이해하기 위해 예제로 주어진 트리를 그려봤다. 루트가 주어지기에 자연스럽게 계층 구조가 형성된다. 서브트리의 개수는 곧 자기와 자식들의 정점 수를 모두 합친 수였다. 시간복잡도를 따져봤을 때 정점의 개수는 십만이고, 쿼리의 개수도 십만이기에 O(N)이나 O(logN)으로 풀어야할 것 같았다.어떻게하면 한 번의 쿼리 때 logN의 시간복잡도를 가질 수 있을까 고민해보다가 그냥 한 번 전체탐색을 돌려서 모든 정점의 서브트리의 개수를 구한 후 쿼리에 맞춰 답을 출력해주면 될 것 같았다. 서브트리를 구하는 방법은 재귀적으로 자식 노드들을 방문하면서 개수를 구하면 될 것 같아서 바로 코드로 옮겨봤다.우선 트리를 형성하기 위해 ArrayList 배열을 이용하였다. 아래와 같이 주어..

9934번: 완전 이진 트리 상근이는 슬로베니아의 도시 Donji Andrijevci를 여행하고 있다. 이 도시의 도로는 깊이가 K인 완전 이진 트리를 이루고 있다. 깊이가 K인 완전 이진 트리는 총 2K-1개의 노드로 이루어져 있다. (아래 www.acmicpc.net 1. 알고리즘 완전 이진 트리 2. 해결책 중위 순회의 중심이 루트인 것을 이용 3. 접근한 방법 해야될 일 : 중심 순회 결과로 트리 구성하라 중위 순위 결과를 가지고 알아낼 수 있는것이 뭐지? DFS 탐색과 결과가 같다. 하지만 루트는 어떻게 알아내고, 트리관계는 어떻게 알아내지? -> 불가능 인덱스를 이용할까. 이 문제는 완전 이진 트리. 자식 노드는 부모 인덱스 i의 2_i, 2_i+1이다. 부모 인덱스는 어떻게 구하지? 이 문제..