codeforce/#635 (Div.2) (1) 썸네일형 리스트형 Codeforces Round #635 (Div. 2) C. Linova and Kingdom 문제 왕궁에는 n개의 도시가 있고, n-1개의 양방향 도로를 도시에 연결한다. 도시는 1번부터 n번까지 숫자가 붙여져있다. 1번 도시가 수도이며, 왕국은 트리 구조이다. 여왕은 정확히 k의 도시에 산업을 발전시키며 다른 도시들은 관광산업을 발전시킨다. 회의는 1년에 한번 수도에서 진행되는데, 각 산업 도시에서는 대표들을 수도로 보낸다. 대표들은 최단 경로를 따라서 수도에 이동한다. 관광도시를 여행하는 것은 즐겁고, 각 대표의 행복도는 수도에 이동하는 동안 방문한 관광도시의 개수이다. 여왕은 k의 산업도시를 잘 배치해 대표들의 행복도의 합을 최대로 하고 싶다. 풀이 산업도시가 수도와 얼마나 떨어져 있는지, 즉 depth 값이 각 산업도시의 행복도이다. DFS로 모든 노드를 방문하여, Depth의 내림차순으.. 이전 1 다음