All Tracks Algorithms Dynamic Programming Problem

Toll charges

Algorithms, DFS, Dynamic Programming, Trees


There are \(N\) friends living in \(N\) different cities. These cities are connected by \(N-1\) roads such that it is possible to reach any city from another city. Each road connects two different cities \(x\) and \(y\). The toll charge of using these roads to go from city \(x\) to city \(y\) can be different from the toll charge of using these roads to go from city \(y\) to city \(x\).

If all \(N\) friends want to meet you, then they can meet in any city. One of your friends can remove toll charges of up to \(K\) roads. Determine the minimum total toll charge your friends have to pay. Each friend is coming in his own vehicle, so everyone is paying a separate toll charge.

Note: No one pays the toll charge for a road for which toll charges were removed.

Input format

  • First line: A single integer \(T\) denoting the number of test cases
  • For each test case:
    • First line: Two integers \(N\) and \(K\) denoting the number of cities and the maximum number of roads on which toll charges are removed respectively
    • Next \(N-1\) lines: Four integers \(x\)\(y\)\(a\), and \(b\)
      Note: Here, cities \(x\) and \(y\) are connected by some road. The toll charge on the road that is used to travel from city \(x\) to city \(y\) is \(a\) and the toll charge when this road is used to travel from city \(y\) to city \(x\) is \(b\).

Output format

For each test case, print the minimum total toll charge that must be paid to meet in a city.


\(1\le T \le 10\)

\(1\le N \le 10^{4}\)

\(0\le K \le N-1\)

\(1 \le x, y \le N,\ 1 \le a, b \le 10^{9}\)

4 1
1 2 10 1000
2 3 10 1000
2 4 10 1000
2 0
1 2 4 5
4 0
1 2 1 1
3 1 5 5
3 4 1 10
4 1
1 2 1 1
3 1 5 5
3 4 1 10

First Sample: Here clearly using roads to move from city 2 to 1, or from city 3 to 2 or from city 4 to 2 is very costly (1000). Here remove the toll charge of road connecting cities 2 and 4 (now friend at city 4 can come to city 2 without paying any toll charge). Now it is optimal for all friends to meet at city 3. Toll charge paid to move from city 1 to city 3 is 20, from city 2 to city 3 is 10 and from city 4 to city 3 is 10. So total toll charge is 40.

Second Sample: Here friend from city 1 move to city 2 and pay a toll charge of 4.

Third Sample: Here it is optimal to meet at city 4. Toll charge paid to move from city 1 to city 4 is 6, from city 2 to city 4 is 7 and from city 3 to city 4 is 1. So total toll charge is 14.

Time Limit: 3.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, R(RScript), Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic


Initializing Code Editor...
Your Rating:


This Problem was Asked in


Challenge Name

November Circuits '19

View All Notifications