¿La página no carga? Prueba haciendo clic aquí.
Placeholder

#8504
Subtarea

전기차 충전소 3.5s 1024MB

Problemas

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

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

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

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

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

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

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

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

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


Entrada

첫 줄에 도시의 개수 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)


Salida

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


Subtarea

# Puntaje Condición
#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

추가 제한 조건 없음


Ejemplo #1

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

Ejemplo #2

3 1
0 1 1
1 2 1
0
2
0

Fuente

CEOI 2024
Debes iniciar sesión para escribir código.