Unique Color Sequences on a Tree

In the fantasy world of Youkai, Youxiang is the most popular moe girl. On her 2600th birthday, a crowd of fans gathers at the sunflower field in front of her house to celebrate. The field consists of n plots which are connected by exactly n-1 edges forming a tree structure. Each of the n fans stands on one plot wearing a colored outfit. There are c different colors, labeled with integers from 0 to c-1.

A planned performance goes as follows. Two fans, A and B (which may be the same), are selected. The fans located on the unique simple path from A’s plot to B’s plot (including both endpoints) will jump in sequence. This creates a list of colors that Youxiang can enjoy. Note that the ordered pair (A,B) is considered different from (B,A) even if they produce sequences that are reversals of each other.

The fans initially intended to have every ordered pair try the performance, but soon worried that many identical color sequences might be produced, leading to aesthetic fatigue. Now, they wonder: How many distinct color sequences can be observed among all possible ordered pairs?

Note: The tree is special in that no plot is adjacent to more than 20 other plots.

inputFormat

The first line contains two integers n and c, where n is the number of plots (and fans) and c is the number of colors available.

The second line contains n integers: the colors of the fans standing on plots 1 through n (each integer is between 0 and c-1).

Each of the following n-1 lines contains two integers u and v, indicating that there is an edge connecting plot u and plot v (1-indexed).

outputFormat

Output a single integer: the number of distinct color sequences that can be observed.

sample

3 3
0 1 2
1 2
2 3

9