# "A delivery company has n depots numbered 0 ... n-1, connected by n-1 two-way roads so that every depot can reach the HQ at depot 0 (the road network forms a tree). Every depot except the HQ has exactly ONE package that must be driven to the HQ. Each van holds up to `seats` packages, and driving a van across ONE road costs 1 litre of fuel. Vans may combine loads: when routes meet, packages can be pooled into fewer vans.
 
# Given the roads as pairs [a, b] and the value `seats`, return the minimum total litres of fuel needed to bring every package to depot 0.
 
# (1 <= n <= 10^5; roads.length == n-1; 1 <= seats <= 10^5.)
 
# Example 1:
# Input: roads = [[0,1],[0,2],[0,3]], seats = 5
# Output: 3
# Explanation: Depots 1, 2, 3 each drive their package one road to depot 0: 1 + 1 + 1 = 3 litres.
 
# Example 2:
# Input: roads = [[3,1],[3,2],[1,0],[0,4],[0,5],[4,6]], seats = 2
# Output: 7
# Explanation: Packages pool as they move toward 0; with 2 seats per van the total works out to 7 litres.
 
# Example 3:
# Input: roads = [], seats = 1
# Output: 0
# Explanation: Only the HQ exists; nothing to deliver."
 
 
 

IyAiQSBkZWxpdmVyeSBjb21wYW55IGhhcyBuIGRlcG90cyBudW1iZXJlZCAwIC4uLiBuLTEsIGNvbm5lY3RlZCBieSBuLTEgdHdvLXdheSByb2FkcyBzbyB0aGF0IGV2ZXJ5IGRlcG90IGNhbiByZWFjaCB0aGUgSFEgYXQgZGVwb3QgMCAodGhlIHJvYWQgbmV0d29yayBmb3JtcyBhIHRyZWUpLiBFdmVyeSBkZXBvdCBleGNlcHQgdGhlIEhRIGhhcyBleGFjdGx5IE9ORSBwYWNrYWdlIHRoYXQgbXVzdCBiZSBkcml2ZW4gdG8gdGhlIEhRLiBFYWNoIHZhbiBob2xkcyB1cCB0byBgc2VhdHNgIHBhY2thZ2VzLCBhbmQgZHJpdmluZyBhIHZhbiBhY3Jvc3MgT05FIHJvYWQgY29zdHMgMSBsaXRyZSBvZiBmdWVsLiBWYW5zIG1heSBjb21iaW5lIGxvYWRzOiB3aGVuIHJvdXRlcyBtZWV0LCBwYWNrYWdlcyBjYW4gYmUgcG9vbGVkIGludG8gZmV3ZXIgdmFucy4KCiMgR2l2ZW4gdGhlIHJvYWRzIGFzIHBhaXJzIFthLCBiXSBhbmQgdGhlIHZhbHVlIGBzZWF0c2AsIHJldHVybiB0aGUgbWluaW11bSB0b3RhbCBsaXRyZXMgb2YgZnVlbCBuZWVkZWQgdG8gYnJpbmcgZXZlcnkgcGFja2FnZSB0byBkZXBvdCAwLgoKIyAoMSA8PSBuIDw9IDEwXjU7IHJvYWRzLmxlbmd0aCA9PSBuLTE7IDEgPD0gc2VhdHMgPD0gMTBeNS4pCgojIEV4YW1wbGUgMToKIyBJbnB1dDogcm9hZHMgPSBbWzAsMV0sWzAsMl0sWzAsM11dLCBzZWF0cyA9IDUKIyBPdXRwdXQ6IDMKIyBFeHBsYW5hdGlvbjogRGVwb3RzIDEsIDIsIDMgZWFjaCBkcml2ZSB0aGVpciBwYWNrYWdlIG9uZSByb2FkIHRvIGRlcG90IDA6IDEgKyAxICsgMSA9IDMgbGl0cmVzLgoKIyBFeGFtcGxlIDI6CiMgSW5wdXQ6IHJvYWRzID0gW1szLDFdLFszLDJdLFsxLDBdLFswLDRdLFswLDVdLFs0LDZdXSwgc2VhdHMgPSAyCiMgT3V0cHV0OiA3CiMgRXhwbGFuYXRpb246IFBhY2thZ2VzIHBvb2wgYXMgdGhleSBtb3ZlIHRvd2FyZCAwOyB3aXRoIDIgc2VhdHMgcGVyIHZhbiB0aGUgdG90YWwgd29ya3Mgb3V0IHRvIDcgbGl0cmVzLgoKIyBFeGFtcGxlIDM6CiMgSW5wdXQ6IHJvYWRzID0gW10sIHNlYXRzID0gMQojIE91dHB1dDogMAojIEV4cGxhbmF0aW9uOiBPbmx5IHRoZSBIUSBleGlzdHM7IG5vdGhpbmcgdG8gZGVsaXZlci4iCgoK