트리와 쿼리 연습

[2016.11.02 초판]

[2017.10.05 트리와 쿼리 7/11 추가]

https://www.acmicpc.net/contest/scoreboard/195

시간이 남을때마다 하긴 했는데... 너무 힘든 연습이었다 ㅠㅠ

아주 간략하게 풀이를 설명한다. 

트리와 쿼리 2

Sparse table로 level ancestor를 빠르게 구할 줄 안다면, 간단한 케이스 분석으로 풀 수 있다.

트리와 쿼리 1 / 3

Heavy Light Decomposition으로 풀 수 있다. 1번의 경우 range max segment tree, 3번의 경우 std::set으로 해결 가능하다. 어렵지 않고 개념도 유용하니 모른다면 배워보자. 

https://blog.anudeep2011.com/heavy-light-decomposition/

트리와 쿼리 1 구현 : https://gist.github.com/koosaga/fe8d275e65777e9bc86204477fb8f478

트리와 쿼리 4 / 5

Centroid Decomposition (트리 분할 정복)을 사용해서 오프라인으로 풀 수 있다. Centroid Decomposition에 대해서 잘 모른다면 IOI 2011 Race를 풀어보자. (문제) 

두 문제의 공통 아이디어는, 각각의 정점마다 처리해야 하는 쿼리들을 저장한 후, 트리 분할 정복 과정에서 현재 보는 트리에 있는 쿼리들을 전부 모은다. 이후 O(|트리 크기| * lgN + |쿼리 크기| * lgN) 정도의 시간에 centroid를 지나는 경로들을 모두 고려해서 답을 갱신해준다. 

centroid를 지나는 경로들을 고려하는 과정을 서술한다.

 * 4번의 경우에는, priority queue나 std::set 등으로 현재 white 노드와의 centroid와의 거리를 관리한다. 지름 질의가 들어오면 첫번째 최댓값과 두번째 최댓값을 반환해서 max 값을 갱신해준다. 첫번째와 두번째 최댓값은 다른 서브트리에서 유래해야 하는데, 적절하게 처리하자. 

 * 5번은 4번보다 조금 더 쉽다. 다른 서브트리에서 유래할 필요가 없어서, 단순히 priority queue로 루트에서 가장 가까운 white 노드를 관리하면 풀 수 있다.

각각의 노드와 쿼리는 위 프로세스에 lgN번 관여되므로 시간 복잡도는 O((N+Q)lg^2N) 이다. 

트리와 쿼리 6

내가 푼 것중에 가장 어렵고 재미있는 문제였다. std::set iterator를 헷갈린 후 몇시간 동안 그 코딩미스를 찾지 못한 바람에, 대회 중에는 풀지 못했다. 

문제를 보면 동적 연결성 문제처럼 굉장히 무섭게 생겼고, 실제로 쿼리가 들어오면 부모 자식 전부 봐줘야 하니까 상당히 힘들다. 하지만, 이를 자식에 관한 문제로 치환해 줄 수가 있는데, 트리와 쿼리 3에서 짰던 Heavy-Light Decomposition을 그대로 활용해서, 부모가 본인과 같은 색깔일 때까지 계속 올라가주면 된다. 이제 서브트리에서 도달 가능한, 자신과 같은 색을 가진 노드만 관리하면 된다.

이 값을 DP + HLD 자료 구조로 관리할 수 있다. DP1[i] = i번 노드가 흰색이고 나머지는 다 현상태일때, i의 서브트리 중 i에서 도달가능한 노드 수 라고 정의하자. (검은색에 대해서도 똑같이) 이 DP값을 알고, 잘 관리할 수 있다면, 개수 세는 쿼리는 쉽게 해결할 수 있다.

DP에 대해서 열심히 관찰을 하면 이를 경로 쿼리만으로 관리할 수 있다. 흰색 노드가 검은색으로 바뀐 경우를 예시로 들자. 

 * 정점 v에서 같은 색깔일 때까지 계속 부모로 올라간 결과를 ladder(v)라 정의한다.

 * 부모가 검은색 노드면, DP1[parent(v)] 에서 DP1[v]를 빼고, DP2[parent(ladder(v))] - DP2[parent(v)] 에서 DP2[v] 를 더해준다.

 * 부모가 흰색 노드면, DP1[parent(ladder(v))] - DP1[parent(v)] 에서 DP1[v]를 빼주고, DP2[parent(v)] 에서 DP2[v] 를 더해준다.

경로 쿼리는 HLD로 O(lg^2N)에 할 수 있다. 고로 쿼리당 O(lg^2N) 정도에 문제가 해결된다. 

트리와 쿼리 7

6번하고 비슷한데 훨씬.. 더럽다. 적어도 내 풀이는 그렇다. Link Cut Tree인 줄 알았는데 실제로는 크게 도움이 안 되는 거 같다. 다만 그걸 쓴 풀이도 있다.

이 문제는 먼저 HLD를 해 주고 시작하자. DP를 다음과 같이 정의한다.

 * DP1[i] = i번 노드가 흰색이고 나머지는 다 현상태임을 가정하자. i번 노드 + i번 노드의 체인이 향한 서브트리를 제외한 나머지 서브트리 정점들 중 최댓값

예를 들어서 

1 - 2 - 3 - 4 - 5 - 6 - 7 (체인 1)

|

8 - 9 - 10 (체인 2)

|

11 (체인 3)

.. 와 같은 걸 생각한다면, DP[1]은 {1, 8, 9, 10, 11} 의 최솟값을 저장하고 있다.

DP2[i]는 i번 노드를 검은색이라고 하고 동일하게 정의한다. 이 해괴한 정의는, 체인 내부에서 도저히 관리가 안돼서 체인을 어떻게든 빼고 생각해야겠다는 절박함에서 나왔다 (...)

쿼리는 일단 6번처럼 ladder(v)를 타고 올라가 주자. 단순히 DP[v]에 접근하면 체인 쪽 서브트리를 볼 수 없으니, 체인 쪽으로 내려간 DP도 접근하고 계속... 검은 정점이 나올 때까지 계속한다. 결국 한 체인의 구간 쿼리로 바뀌어서 RMQ로 해결할 수 있다.

가중치 업데이트는.. 너무 길게 설명하면 답 없으니 대충 설명한다. 결국 현재 정점 - 루트를 잇는 path의 DP값만 갱신하면 되니 루트로 올라가 준다. 각 정점에 대해서 priority queue를 갖고 있는데, (std::set으로 구현하는 게 나을 것이다) priority queue에 들어 있는 원소들은 i번 노드의 가중치와, i번 노드의 자식 서브트리의 최댓값들이 들어가 있다. priority queue의 최댓값이 DP값임 역시 알 수 있다. 이제 방법을 설명하자면, 일단 현재 정점의 노드 값을 갱신해 주고, pque도 바꿔주고, 다른 색이 나오기 전까지 DP값과 priority queue를 올바른 값으로 갱신해 준다. 이걸 계속 반복해 주면 된다. 

색상 변경은 가중치 업데이트랑 비슷한데, 할게 조금 더 많다.. 설명은 생략. DP 정의를 저렇게 딱 잡은 다음에, 저 DP 조건을 만족하게 정말 열심히 해 주면 풀리는 문제였다...

트리와 쿼리 8

Persistent Segment tree로 풀 수 있는 문제로 옛날에 풀이를 썼던 문제다.

트리와 쿼리 9

Mo's Algorithm이라고 쿼리를 적당히 정렬해서 사용하는 괴랄한 sqrt decomposition 방법이 있다. 모르면 배우자. 트리에서 똑같이 일반화 할수가 있는데... euler tour 순으로 번호를 매긴 후 각각에 정점에 들어간 시간을 in(v), out(v) 라고 하자. 이제 경로 쿼리를 make_pair(in(v) / B, out(v)) 순으로 정렬하고, 경로를 트리의 최단 경로를 따라서 적당히 갱신해주면서 이동하면 된다... 왜 되냐면, euler tour의 이동 거리는 최단 거리보다 무조건 길거나 같기 때문. 

코딩을 할 때는, 기존 시작점 - 기존 끝점 -> 새 시작점 - 기존 끝점 -> 새 시작점 - 새 끝점 이런 식으로 한 점을 고정시켜서 이동하면 편리하게 짤 수 있었다. 임의의 경로 안에 정점이 속하는 지를 O(1)에 판단하는 In_Path(경로LCA, 경로시작, 경로끝, 정점) 함수를 정의하면 좋다.

트리와 쿼리 10

1 / 3과 똑같이 HLD를 쓰는 문제지만 전역에 박아야 하는 세그먼트 트리가 좀 골때린다. 그래도 괜찮은 코딩 연습 문제.

트리와 쿼리 11

마지막 문제는 Link Cut Tree 연습 문제이다. 기본적인 Link Cut Tree 연산을 알면 해결할 수 있고, 이에 대해서는 이 블로그에 매우 잘 나와 있으니 한번 보자.