1번 노드가 루트이고 가중치가 부여된 노드가 N개 있다.

i번째 노드에 부여된 가중치는 v_i이다.

상수는 이 트리에서 정점을 적당히 선택해서 힙으로 만들고 싶다.

그래서 상수는 다음 조건을 만족하는 정점 집합을 선택하기로 했다.

선택된 노드들이 부분트리를 이룰 필요는 없다. 단지 아래 조건을 만족하면 된다.

"집합에 포함된 모든 정점쌍 i, j에 대해서, 정점 i가 정점 j의 조상이라면, v_i > v_j이다." (부등호에 등호가 없음에 유의하자)

가능한 정점 집합들 중 정점 갯수의 최댓값을 구해 상수에게 알려주자.

Heaps from Trees timer 1s memory 128MB

Heaps from Trees 1s 128MB