All Tracks Algorithms Dynamic Programming Problem

Forming Teams
Tag(s):

Algorithms, Binary search algorithm, Dynamic Programming, Medium, Tree

Problem
Editorial
Analytics

MacroSoft, one of the largest company in the world has recently got a huge fund for a large project. Mr. X, the CEO of MacroSoft is very excited about the project and is planning to divide all of his employees into different teams to distribute the tasks. In MacroSoft each employee has got exactly one supervisor except Mr. X. Of course! Why would he need one? He’s the CEO! Also, each of the employees including Mr. X has got a rank in the company. As you are the project manager, you need to help Mr. X dividing the employees into maximum K teams in such a way that each member belongs to exactly one of the teams and the maximum imbalance value among all the teams is minimized.

You can form a team with any subset of employees S if it satisfies the following conditions:

  1. There should be exactly one employee w in the subset S whose supervisor doesn’t exist in S and w will be the team leader of that team.

  2. For any employee u (excluding w), if u exist in the set S, then the supervisor of u must also exist in the set S.

Now the imbalance value of a team depends on the rank of all the team members. For each employee, u, take the difference between the rank of u and the rank of the team leader. The imbalance value of the team is the maximum values among all the differences. You have to minimize the maximum imbalance value among all the teams.

Constraints

  • 1 <= T <= 3
  • 1 <= N <= 1000
  • 1 <= K <= N
  • 0 <= Ai <= 10^9

Input Format

The first line contains T, the number of test cases. The first line of a test case contains two integers N and K. N is the number of employees in the company and K is the maximum number of teams you can form. The second line contains N space separated integers representing the array A, where Ai is the rank of employee i. Each of the next N-1 lines contains two integers u and v, which means that u is the supervisor of employee v.

Output Format

For each test cases, print a single integer, the maximum imbalance value of the team which is minimized.

SAMPLE INPUT
1
8 2
20 15 8 25 5 3 2 10
1 2
1 3
1 4
3 5
5 6
5 7
3 8
SAMPLE OUTPUT
6
Explanation

We can form two teams. The employees in the first team are 1, 2 and 4. The imbalance value of the team is 5. All the remaining members form the second team. The imbalance value of this team is 6. Among these two teams, the maximum imbalance value is 6, so this is our answer. There’s no other optimal way where we can minimize this value anymore.

Time Limit: 2.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, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

August Circuits '18

OTHER PROBLEMS OF THIS CHALLENGE
通知
View All Notifications

?