Minimize Blocked Roads CodeChef Solution | CodeChef Problem Solution 2022

[Solution] Minimize Blocked Roads CodeChef Solution | CodeChef Problem Solution 2022

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

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

Solution Click Below:-  CLICK HERE

Initially, city numbered 1$1$ 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 1$1$) you need to block such that at most K$K$ cities are infected at the end.

My very 1st contest! CodeChef Solution

Chess Ratings CodeChef Solution

[Solution] Recent contest problems CodeChef Solution

A or B CodeChef Solution

Closest Vowels CodeChef Solution

Minimize Blocked Roads CodeChef Solution

If it is not possible that at most K$K$ cities are infected, print −1$-1$.

Input Format

• The first line contains an integer T$T$ denoting the number of test cases. The T$T$ test cases then follow.
• The first line of each test case contains two space-separated integers N$N$ and K$K$, as given in the statement.
• Each of the next (N−1)$(N-1)$ lines consists of 3$3$ space-separated integers U$U$, V$V$, and X$X$ denoting that there exists a road between cities U$U$ and V$V$ with a value X$X$ (0$(0$ or 1)$1)$.

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 K$K$ cities are infected at the end.
If it is not possible that at most K$K$ cities are infected, print −1$-1$.

Constraints

• 1≤T≤1000$1\le T\le 1000$
• 1≤N≤2⋅105$1\le N\le 2\cdot {10}^5$
• 1≤K≤N$1\le K\le N$
• 1≤U,V≤N$1\le U,V\le N$ and U≠V$U\ne V$.
• 0≤X≤1$0\le X\le 1$
• Sum of N$N$ over all cases does not exceed 2⋅105$2\cdot {10}^5$.