Gu of Love

View as PDF

Submit solution

Points: 20
Time limit: 1.8s
Java 8 3.5s
Memory limit: 512M

Author:
Problem type

The Gu of love is a mystical substance produced only in the Southern kingdom of China. The princess of the Southern Kingdom wishes to use it to revive her love, Pingchiu Yuechu. To experiment, she has collected a group of people, some of whom know each other. She notices that the connections between these groups of people form a tree structure.

She wants to divide these people into exactly K groups, such that the total absolute difference between the number of males and females in each group is as large as possible. Moreover, each person in each group must know each other person in the group directly or indirectly (through multiple connections between other people in the group).

Given N, the number of people, and K, the number of groups (1 \le K \le N \le 200), each person's gender and N-1 connections between them, figure out this value.

Input Specification

Line 1: Two integers N and K (1 \le K \le N \le 200)
Line 2: N integers, either 1 or 0, the gender of the i-th person.
Next N-1 Lines: Two integers a_j and b_j, signifying that a_j and b_j are connected.

Sample Input

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

Sample Output

5

Comments

There are no comments at the moment.