JOI Finals
-
JOI Finals 2019 Unique CitiesJOI Finals 2020. 6. 21. 16:14
문제를 요약하자면, 트리가 주어지고 각 정점별로 색깔이 주어졌을 때, 각 정점별로 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. ..