Maximum Pairs Divisible by K

You are given a tree with \( N \) nodes where each node has an associated integer value. In addition, a positive integer \( K \) is provided. Your task is to form as many pairs of nodes as possible such that the sum of the two node values in each pair is a multiple of \( K \). Each node may be used in at most one pair.

Note that the tree is represented by \( N-1 \) edges, but the structure of the tree does not affect the pairing process. You only need to consider the node values. A pair of nodes \( (a, b) \) is valid if: \[ a+b \equiv 0 \pmod{K} \]

For example, if \( N = 5 \), \( K = 3 \), values are [1, 2, 3, 4, 5] and the edges are given but not used in the pairing, the answer is 2 since there are 2 valid pairs.

inputFormat

The input is given via stdin with the following format:

N K
v1 v2 ... vN
a1 b1
a2 b2
...
a{N-1} b{N-1}

Where:

• N: The number of nodes.
• K: The divisor for checking the sum.
• v1, v2, ..., vN: The values associated with each node.
• a_i b_i: An edge connecting node a_i and node b_i.

outputFormat

Output a single integer via stdout that represents the maximum number of pairs of nodes whose values sum to a multiple of \( K \).

5 3
1 2 3 4 5
1 2
1 3
3 4
3 5

2