페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#4808
서브태스크

맛집 추천 3s 1024MB

문제

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에 속한 맛집들의 선호도의 합이 최대인 집합을 찾아, 그때 선호도의 합을 출력하는 프로그램을 작성하라.


입력

첫 번째 줄에 두 개의 정수 N과 M이 공백 하나를 사이로 두고 주어진다.

다음 N − 1개의 줄에는 KOI 나라의 길이 잇는 두 도시의 번호를 나타내는 정수 a와 b가 공백 하나를 사이로 두고 주어진다.

다음 M개의 줄에는 맛집에 대한 정보가 주어진다. 이 중 i (1 ≤ i ≤ M)번째 줄에는 세 개의 정수 c_i, d_i, g_i가 공백 하나를 사이로 두고 주어진다.​ 

제약 조건

  • 주어지는 모든 수는 정수이다.

  • 1 ≤ N ≤ 10^5

  • 1 ≤ M ≤ 10^5

  • 모든 i (1 ≤ i ≤ M)에 대해: 0 ≤ d_i ≤ N − 1, 1 ≤ g_i ≤ 10^9


출력

첫 번째 줄에 문제의 조건을 만족하는 맛집의 집합 중 선호도의 합을 최대화하도록 집합을 골랐을 때의 선호도의 합을 출력한다.


부분문제

번호 점수 조건
#19점

1 ≤ i ≤ N − 1 에 대해서, i번 정점과 i + 1번 정점이 간선으로 연결되어 있다.

#211점

N, M ≤ 20.

#317점

N, M ≤ 2\,000.

#410점

N ≤ 2\,000.

#58점

2 ≤ i ≤ N에 대해, ⌊i / 2⌋​번 정점과 i번 정점이 간선으로 연결되어 있다.

#612점

차수가 3 이상인 정점은 많아야 하나뿐이다.

#733점

추가 제약 조건이 없다.


예제 

8 5

1 2

2 3

3 4

4 5

5 6

4 7

4 8

3 2 40

6 0 5

8 0 5

2 1 16

5 1 32
53

출처

KOI 2차 2021 고4|koi
로그인해야 코드를 작성할 수 있어요.