頁面無法載入？點擊這裡可能會修復。
Placeholder

#8504
子任務

전기차 충전소 3.5s 1024MB

問題

정올국은 N개의 도시가 N-1개의 도로로 이어진 트리 모양의 국가이다.

각 도시는 차례대로 0번, 1번, ..., N-1번 번호를 매겼다.

또한 각 도로는 도시 u_i와 v_i를 이으며, 길이는 l_ikm이다.

정올국에는 매일 N^2대의 전기차가 다니며, 이 전기차들은 각각 서로 다른 시작점과 도착점을 가지고 있다.

즉, 어떤 두 도시를 잡아도, 그 두 도시를 각각 시작점과 도착점으로 하는 전기차가 정확히 한 대씩 있다.

모든 전기차는 연비가 같다. 구체적으로, 이 차들의 연료를 가득 충전하면 최대 Kkm 달릴 수 있다.

모든 전기차들은 시작점과 도착점 사이를 최단경로를 따라 움직이며,
만약 다음 도시로 남은 연료를 사용해 이동하지 못할 경우,
지금 있는 도시에서 연료를 가득 채운다.

연료가 0인 채로 딱 도시에 도착하는 것은 허용한다.

각 도시에서 충전하는 전기차의 개수를 구해보자.


輸入

첫 줄에 도시의 개수 N과, 연비 K가 주어진다. (1\leq N\leq 70000, 1\leq K\leq 10^9)

그 다음 N-1개의 줄에 걸쳐 도로의 정보가 u_i, v_i, l_i의 순서로 주어진다. (0\leq u_i, v_i<N, 1\leq l_i\leq K)


輸出

0번, 1번, ..., N-1번 도시에서 충전하는 전기차의 대수를 한 줄에 하나씩 순서대로 출력하여라.


子任務

編號 分數 條件
#118分

N\leq 1000, K\leq 1000

#28分

각 도시와 연결된 도로의 개수는 최대 2개이다, 모든 i에 대해 l_i=1

#310分

각 도시와 연결된 도로의 개수는 최대 2개이다.

#412分

각 도시와 연결된 도로의 개수는 최대 10개이다, K\leq 10

#517分

K\leq 10

#635分

추가 제한 조건 없음


範例 #1

6 2
0 1 1
1 2 1
2 3 1
3 4 2
4 5 1
0
3
3
12
8
0

範例 #2

3 1
0 1 1
1 2 1
0
2
0

來源

CEOI 2024
需要登入才能撰寫程式碼。