JOI Finals 2019 Unique Cities

문제를 요약하자면, 트리가 주어지고 각 정점별로 색깔이 주어졌을 때, 각 정점별로 Unique한 정점에 있는 색의 종류를 출력하라는 문제이다. 여기서 어떤 정점 y가 x에 대해 Unique하다는 것은, 임의의 정점 z≠y에 대해서 d(x, y)≠d(x, z)임과 동치이다. 여기서 d(u, v)는 u와 v 사이의 최단 경로의 길이를 뜻한다.

 

Subtask 1 (4점)

N≤2000이므로, 모든 정점에 대해 dfs혹은 bfs를 통해 Naive하게 답을 구할 수 있다. 시간복잡도는 O(N^2).

 

Subtask 2+3 (68점)

본인이 접근한 방법으로는 Subtask 2와 3을 푸는데 풀이상 큰 차이가 없어서 한번에 작성하도록 하겠다. 이 문제를 풀기 위해 핵심적인 lemma를 하나 제시하겠다.

 

Lemma 1. 임의의 정점 v에 대해 Unique한 모든 정점들은, v에서 가장 멀리 떨어진 정점을 u라 하면 v와 u를 잇는 경로 위에 놓여있다.

pf) 귀류법을 사용한다. v와 u를 잇는 경로 위에 없으면서  v에 대해 Unique한 임의의 정점 z가 존재한다고 가정하자. v와 u를 잇는 경로 상에는 v와 떨어진 거리가 k(k는 자연수, k≤d(v, u))인 정점 w가 항상 존재한다. 고로, d(v, z)>d(v, u)인데, 이는 u가 v에서 가장 멀리 떨어진 정점이라는 전제에 모순이다. 따라서 조건을 만족하는 z는 존재하지 않는다.

 

만약 가장 멀리 떨어진 정점이 두개 이상이라면 어떻게 될지 생각해 볼 수 있다. Unique한 정점은 결국 해당되는 경로들의 교집합 위에만 존재할 수 있다. 증명은 위와 비슷하므로 생략하겠다. 이 관찰을 토대로, 가장 멀리 떨어진 정점을 한개만 찾으면, 그 경로 위에만 있는 정점들만을 탐색해주면 된다는 것을 알 수 있다.

 

추가적으로 v에 대해 가장 멀리 떨어진 정점 u에 대한 lemma도 제시하도록 하겠다.

 

Lemma 2. 임의의 정점 v에 대해 트리 지름의 양 끝점 중 적어도 하나는 v에서 가장 멀리 떨어진 정점 u가 될 수 있다.

pf) 이 또한 귀류법을 사용한다.

흰 정점들로 이루어진 사슬은 트리의 지름을 나타낸다.

트리의 지름의 양끝으로 향하지 않는 모든 경로는 다음의 두가지 케이스로 나뉜다. 각각의 경로가 d(v, A)보다 크다고 가정하고 모순을 찾아보자.

 

1) 트리의 지름과 겹치지 않는 경우 (빨간색 경로)

d(v, u)>d(v, A)를 만족하므로, w를 v와 u의 LCA라 했을 때 d(w, u)>d(w, A)이고, d(R, u)-d(R, w)>d(R, w)+d(R, A)이므로, d(R, u)>d(R, A)라는 결론을 얻게 된다. (∵d(R, w)>0) 근데 그렇다면 트리의 지름은 R에서 A로 가는 경로가 아니라 R에서 u로 가는 경로를 포함할 것이므로 모순이다.

 

2) 그 이외의 경우 (파란색 경로)

d(v, u)>d(v, A)를 만족하므로, d(v, S)+d(S, u)>d(v, S)+d(S, A)이고, d(S, u)>d(S, A)이다. 그렇다면 트리의 지름은 S에서 A로 가는 경로가 아니라 S에서 u로 가는 경로를 포함할 것이므로 모순이다.

 

따라서, 각 정점에 대해 가장 먼 정점의 위치가 트리의 양 끝 정점 두개중 하나로 귀결된다. 이를 이용해 트리의 지름 양 끝점으로부터 각각 dfs를 통해 Unique한 정점들을 모두 구할 수 있다.

 

A에서 dfs를 해서 현재 정점 v에 도달했을 때의 상황, v에 대해 Unique한 점의 개수는 2개이다.

dfs 전에 전처리를 통해 각 subtree의 최대 깊이를 구해두자. 현재 노드에서 자식 노드로 dfs를 할 때, 해당되는 자식 노드 이외의 다른 자식 노드들에 대해 각 subtree 깊이의 최댓값을 구할 수 있다. 그 최댓값이 x라면, x번째 조상 노드까지는 Unique한 정점이 될 수 없다. 이는 구간에 1을 더하고 빼는 연산이 있고, 해당 구간의 0의 개수를 구할 수 있는 연산을 지원하는 Segment Tree와 Lazy Propogation으로 구현할 수 있다. (IOI 2018 Day 1 Seats에서 사용하는 Segment Tree와 완전히 동일하다.) Subtask 2의 경우 0의 개수가 1개 이상이면 1, 아니면 0을 출력해주면 되고, Subtask 3의 경우 0의 개수를 출력해주면 된다. 이때 트리의 지름 두곳에서 시작한 dfs에서 각각 구한 답의 Max가 실제 Unique한 정점들의 개수임에 주의하자. 시간복잡도는 O(NlogN).

 

Subtask 4 (100점)

Subtask 2+3의 풀이를 조금만 보완하면 된다. 사실 각 정점별로 업데이트해야되는 값은 많아봤자 두개이고, 이를 작은것부터 업데이트한다. 이렇게 하면 dfs 과정에서 정점별로 가려지는 구간에는 단조성이 보장된다. 조금 더 구체적으로는, 각 정점에서 본인의 k번째 부모까지 지워야 한다고 가정하면, 그 k값은 dfs의 깊이가 깊어질수록 단조 감소한다. 따라서 스택을 이용해 각 순간별로 가려진 곳의 집합을 관리할 수 있고, 시간복잡도는 O(N).