Minimize Blocked Roads solution codechef

Minimize Blocked Roads solution codechef

Given a network of NN cities (numbered from 11 to NN) and (N1)(N−1) roads arranged in a tree format with the root at city 11.
Each of the (N1)(N−1) roads is assigned a value of either 00 or 11.

  • If the value of a road is 00, it cannot be blocked by the government.
  • If the value of a road is 11, it may or may not be blocked depending on the decision of the government.

Initially, city numbered 11 is infected by a virus. The infection spreads from an infected to an uninfected city only if all the roads present on the shortest path between the cities are unblocked.

The government wants to control the number of infected cities and has asked you to devise a plan. Determine the minimum number of roads (with value 11) you need to block such that at most KK cities are infected at the end.
If it is not possible that at most KK cities are infected, print 1−1.

Input Format

Minimize Blocked Roads solution codechef

  • The first line contains an integer TT denoting the number of test cases. The TT test cases then follow.
  • The first line of each test case contains two space-separated integers NN and KK, as given in the statement.
  • Each of the next (N1)(N−1) lines consists of 33 space-separated integers UUVV, and XX denoting that there exists a road between cities UU and VV with a value XX (0(0 or 1)1).
  • CodeChef was created as a platform to help programmers make it big in the world of algorithms, computer programming and programming contests. At CodeChef, we work hard to revive the geek in you by hosting a programming contest at the start of the month and another smaller programming challenge in the middle of the month.

Output Format

For each test case, output a single integer representing the minimum number of roads that need to be blocked such that at most KK cities are infected at the end.
If it is not possible that at most KK cities are infected, print 1−1.

Constraints

Minimize Blocked Roads solution codechef

  • 1T10001≤T≤1000
  • 1N21051≤N≤2⋅105
  • 1KN1≤K≤N
  • 1U,VN1≤U,V≤N and UVU≠V.
  • 0X10≤X≤1
  • Sum of NN over all cases does not exceed 21052⋅105.

Sample Input 1 

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

Sample Output 1

Minimize Blocked Roads solution codechef

1
-1

Explanation

Test Case 11: The road between city 11 and city 33 is blockable. By blocking that road the total number of infected cities, in the end, will be 33 (namely city 1,21,2 and 66) which is less than K=4K=4.

Test Case 22: Even if all the blockable roads are blocked, the total number of cities that will get infected in the end will be 44 (namely city 1,2,3,1,2,3, and 44) which is greater than K=3K=3. Thus, answer is 1−1.

SOLUTION

Click here

Leave a Comment

Your email address will not be published.