KOI나라에는 N개의 도시가 있다. 각 도시에는 1번부터 N번까지의 번호가 붙어 있다.

KOI나라는 구조가 특이해서, 도시를 정점으로 표현하고 길을 양방향 간선으로 표현하면 N개의 정점을 가진 트리가 된다. 트리는 사이클이 없는 연결 그래프이다.

KOI나라에는 총 M개의 맛집이 있으며, 각 맛집에는 1번부터 M번까지의 번호가 붙어 있다. 맛집이 아예 없는 도시가 있을 수도 있고, 맛집이 두 개 이상 있는 도시가 있을 수도 있음에 유의하라.

i (1 ≤ i ≤ M)번 맛집은 c_i번 도시에 있으며, 배달 가능 거리는 d_i이고, 고객 선호도는 g_i이다.

i번 맛집은 c_i번 도시에서부터 d_i개 이하의 길을 거쳐 갈 수 있는 도시들에만 배달을 할 수 있다. 즉, i번 맛집이 배달할 수 있는 도시들의 집합을 R_i라고 하면, R_i = \{j\ |\ d(c_i, j) ≤ d_i\}이다. 여기서 d(a, b)는 a번 도시와 b번 도시의 최단 경로의 길이(두 도시 사이를 이동하기 위해 거쳐야 하는 최소 길의 수)이다.

당신은 배달 앱의 운영자이다. 배달 앱은 맛집들을 추천하는데 서비스의 중복을 피하기 위해서 M개의 맛집 중 다음 조건을 만족하는 맛집들의 집합 S를 고르려고 한다.

임의의 도시 p에 대해서, p는 S에 속하는 두 개 이상의 맛집의 배달 가능한 집합에 동시에 속하지 않는다. 즉, S에 속한 임의의 서로 다른 두 맛집 i와 j에 대해서, R_i ∩ R_j 는 공집합이어야 한다.

위 조건을 만족하는 맛집들의 집합 S 중에서, S에 속한 맛집들의 선호도의 합이 최대인 집합을 찾아, 그때 선호도의 합을 출력하는 프로그램을 작성하라.

#4808 upload 77 done 15 how_to_reg 19 call_split Subtask

맛집 추천 timer 3s memory 1024MB

#4808
Subtask

맛집 추천 3s 1024MB