## Gu of Love

View as PDF

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 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 , the number of people, and , the number of groups (), each person's gender and connections between them, figure out this value.

#### Input Specification

Line 1: Two integers and ()
Line 2: integers, either 1 or 0, the gender of the -th person.
Next Lines: Two integers and , signifying that and 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