루미 알고리즘

#1614다이아Train Mania

PO 2025 훈련 캠프코딩출제 Joshua Andersson영어 원문이 문제가 어렵다면 — 배우는 순서 보기

영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

It is very well known that Julia likes the TV series På spåret. So, it may not come as a surprise that she enjoys traveling by train. Unfortunately, she has recently gone a bit off track, and this once innocent hobby has turned into a manic need to ride trains. The problem is that it is difficult to travel by train as much as she would like since trips take a long time.

Even though she cannot take every train, she tries to travel with as many as possible. After spending hours in her room trying to create the best travel plan, you decide to help her. While the number of trains she takes is not exactly healthy, you prefer that she actually rides trains rather than just planning her train journeys.

Julia lives in the city of Lönnköping, which has N stations numbered from 1 to N. To travel between them, there are two modes of transportation: electric scooters and trains. There are so many electric scooters in the city that she can start a scooter ride from any station. However, she can only ride a scooter along the N-1 roads in the city. It is possible to travel between any two stations using one or more of these roads, meaning the road network forms a tree. Traveling along each road with a scooter takes a certain number of seconds.

She can also take part in the next K train departures. Each train follows a strict schedule: it departs from a specific station at a specific time and arrives at its destination after a certain number of seconds. If Julia is at a station at the exact second a train departs, she can take it if she wants. She will then stay on the train until it reaches its final destination (she cannot bring herself to get off a train before she absolutely has to). If a train arrives at a station at the exact second another train departs, she can make the transfer if she chooses.

Given the road network and the next K train departures, how many trains can Julia take if she plans her journey optimally? Since the plan is set for some time in the future, she is unsure where she will start, so she wants you to calculate the maximum number of trains she can take for each possible starting station. You can assume that she always begins her journey at time 0.

Input

The first line of input contains two integers, N and K (1 ≤ N, K ≤ 10^5), representing the number of stations in Lönnköping and the number of train departures to consider.

The next N-1 lines describe the road network. Each of these lines contains the integers u, v, s (1 ≤ u, v ≤ N, 1 ≤ s ≤ 10^9), meaning there is a road between stations u and v. It takes s seconds to travel from u to v or from v to u using a scooter.

After that, there are K lines describing the train departures. Each of these lines contains the integers u, v, t, d (1 ≤ u, v ≤ N, u ≠ v, 0 ≤ t ≤ 10^9, 1 ≤ d ≤ 10^9), meaning that at time t, a train departs from station u to station v and arrives at station v at time t+d. It is guaranteed that all t values are unique.

Output

Let x_i denote the maximum number of trains Julia can take if she starts her journey at station i. Print x_1, x_2, …, x_N separated by spaces.

Scoring

Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.

GroupPointsConstraints
110N, K ≤ 50, t, d ≤ 100 for all t,d.
25N, K ≤ 50
312N ≤ 1000, K ≤ 200
413N, K ≤ 2000
510K ≤ 2000 and the smallest t is larger than the sum of all s.
62K ≤ 20000
723There is a path between station i and station i+1 for all 1 ≤ i ≤ N-1.
825No additional constraints.

예제

예제 1

입력
3 3
1 2 1
2 3 1
1 3 0 1
1 3 3 2
1 3 6 1
출력
2 1 1 

출처 표기

출처: Programmeringsolympiaden 2025년 훈련 캠프 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.