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

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

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

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

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

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

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

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

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

전기차 충전소 timer 3.5s memory 1024MB

전기차 충전소 3.5s 1024MB