MROADS - Roads Repair


English Vietnamese

Có N thành phố và N-1 cặp đường nối chúng, có duy nhất 1 đường nối 2 thành phố khác nhau.

Đường đã bị xuống cấp và với mỗi đường ta biết 2 số A, B : A(s) thời gian để đi qua đường này và B(s) là thời gian ít nhất để đi qua đường này nếu nâng cấp hết cả đường.

Có 1 lượng tiền đầu tư để sửa đường, với mỗi đoạn đường, kết quả sẽ tỉ lệ với lượng tiền đầu tư. Đầu tư 1 euro cho 1 đoạn đường sẽ giảm thời gian trên đoạn đường đó đi 1s. Tuy nhiên nó không thể giảm quá thời gian tối thiểu B của đoạn đường này.

Cần phân bố lượng tiền trên cho các đoạn đường khác nhau để thời gian cần thiết đi từ thành phố 1 tới thành phố xa nhất (đi mất nhiều thời gian nhất sau khi thực hiện mọi sửa chữa) là nhỏ nhất có thể.

Xác định thời gian nhỏ nhất này.

Input

Dòng đầu gồm 2 số nguyên N và K, 2 ≤ N ≤ 100 000, 0 ≤ K ≤ 1 000 000, số thành phố và lượng tiền (euros)

Sau đó là N-1 dòng, mỗi dòng 4 số nguyên X, Y, A và B, 0 ≤ B ≤ A ≤ 10 000. Nghĩa là có đường đi từ nối X và Y với 2 thông tin A và B như trên.

Output

Thời gian nhỏ nhất cần tìm theo yêu cầu đề bài.

Sample

input 
 
3 200
1 2 200 100
2 3 450 250
 
output
 
450

input
 
5 11
1 2 10 5
1 3 3 2
1 4 9 6
3 5 7 3
 
output
 
6

input
 
11 12
1 2 7 5
1 3 20 15
2 4 10 8
2 5 5 3
2 6 6 2
4 7 3 0
4 8 7 2
5 9 8 4
5 10 9 8
5 11 6 5
 
output
 
17


hide comments
mhamed_resli: 2018-01-30 18:43:56

AC after 6 TLE . nice problem!

Tomek Jurkiewicz: 2017-01-20 13:05:44

@Jelle van den Hooff: solution is O(n lg(k))

coding_express: 2013-05-28 11:06:05

please explain test case no 3
please......

Sigma Kappa: 2011-05-29 12:47:53

@kush sharma: the answer is indeed "17".

Last edit: 2011-05-29 15:04:32
Kush Sharma: 2011-03-19 17:19:51

can u explain the third test case..?
the longest path is 1->2->5->10
and the o/p should be 16

Last edit: 2011-03-19 17:38:35
amaroq: 2009-06-08 08:20:33

'Most distant city' refers to the city to which it takes the most time to get to, rather than deepest in the tree. I found this a bit confusing at first.

Jelle van den Hooff: 2009-06-07 19:24:40

Time limit seems to be rather strict for my O(K lg(n)) (I even think it's more like n lg(n))

Last edit: 2009-06-07 18:31:04

Added by:~!(*(@*!@^&
Date:2009-06-06
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:COI 06