맛집 추천

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

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

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

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

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

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

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

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

• 주어지는 모든 수는 정수이다.
• $ 1 \le N \le 10^{5} $
• $ 1 \le M \le 10^{5} $
• 모든 $ i $ ($ 1 \le i \le M $)에 대해: $ 0 \le d_{i} \le N - 1 $, $ 1 \le g_{i} \le 10^{9} $

1. (9점) $ 1 \le i \le N - 1 $ 에 대해서, $ i $번 정점과 $ i+1 $번 정점이 간선으로 연결되어 있다.
2. (11점) $ N, M \le 20 $.
3. (17점) $ N, M \le 2\,000 $.
4. (10점) $ N \le 2\,000 $.
5. (8점) $ 2 \le i \le N $에 대해, $ \lfloor i / 2 \rfloor $번 정점과 $ i $번 정점이 간선으로 연결되어 있다.
6. (12점) 차수가 $ 3 $ 이상인 정점은 많아야 하나뿐이다.
7. (33점) 추가 제약 조건이 없다.

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

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

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

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