알고리즘 일지

  16748번: Colorful Tree (acmicpc.net) 오일러 투어 테크닉을 이용하여, 트리를 선형으로 핀다음, Map을 통해, 한 서브 트리가 가지는 특정 색깔의 갯수를 세그먼트 트리를 통해 O(log N)에 찾을 수 있다. 자바는 시간이 빠듯하여, 바텀업으로 하는 것을 추천한다. O(N(log N)^2)의 상수를 최대한 줄여야 한다. 여유? 그건 C++ 어떤 하나의 색깔이 추가 될 때, 트리를 최적화 하게 만들어 둔다고 했을 때, 추가 하는 색깔의 위치는, 그 전 색깔을 통해 만들어진 최적화 트리를 통해 만들어진 LCA의 서브 트리 아래에 종속 되어 있거나, 서브트리에 속하지 않는다 . 1. 서브트리 아래에 종속 되어 있을 때 1. 최적화 된 트리 안에 색을 추가하는 경우는 트리의 크기에 변화를 주지 않는다. 2. 최적화 된 트리 바깥에 색을 추가하는 경우는, 서브트리에서 색을 발견 할 때까지 거슬러 올라가, 거리를 더해준다. 2. 서브트리 바깥에 있을 때 1. 특정 노드의 서브트리 안에 색을 발견 할 때 까지 거슬러 올라가 거리를 더해준다.  그 지점이 색의 LCA를 서브트리로 가지고 있는 다면, LCA와의 거리도 더해준다. 특정 색깔의 LCA는 깊이가 가장 높은 노드부터, 루트 노드까지의 경로 선상에 존재하게 된다. 색깔의 LCA는 그 경로 선상에서 서브 트리가 특정 색깔을 모두 가지고 있는 노드 중, 제일 하위 노드이다. 이런 색깔의 LCA는 루트와 특정 색깔의 최하위 노드의 경로 선상에서 파라매트릭 서치를 하면 된다. 이 경우 파라매트릭을 하며, 세그먼트 트리 쿼리를 날리므로, O(log N) ^ 2 이다. 색을 발견 할 때 까지 거슬러 올라 가는 것도, 루트와의 경로에서, 파라매트릭 서치를 하며, 세그먼트 트리 쿼리를 날리면 된다. 색깔에 대한 트리의 크기 응답에는 O(1) 색깔을 바꾸는 데에는 O(log N ^ 2 )가 소요된다. 색깔을 없애는 방법은 그 위치에 대한 색깔정보를 없애 버리고, 새롭게 추가하려는 시도를 ...