P3346 [ZJOI2015] The Fantasy Land Favored by the Gods

Yuuka is the most popular cute girl in all of Gensokyo. Today is her $2600$-th birthday, and countless fans have come to the sunflower field in front of her house to celebrate. The fans are very enthusiastic and spontaneously organized a series of performances for Yuuka. Of course, Yuuka is very happy. At this moment, Yuuka notices something interesting: the sunflower field has $n$ empty plots. In the past, for convenience, Yuuka built $n-1$ edges among these $n$ plots to connect them. That is, these $n$ plots form a tree. There are $n$ fans who have come to the sunflower field. To express their congratulations for Yuuka’s birthday, they chose $c$ colors of clothing, and each color is represented by an integer between $0$ and $c-1$. Each person stands on exactly one plot, and each plot has exactly one person. Thus, the entire sunflower field becomes colorful. Yuuka sees this and feels very happy. One of the planned performances is as follows: select two fans A and B (A and B can be the same), then the fans on the path from A’s plot to B’s plot jump in order (including the endpoints). In this way, Yuuka can see a color sequence whose length is the number of fans on the path between A and B (including A and B). At first, everyone planned to try all pairs of fans. Note: A, B and B, A are different; the sequences they form are exactly reversed. However, someone pointed out that this might lead to some identical color sequences, causing aesthetic fatigue. So they want to ask: on this tree, how many different color sequences can Yuuka possibly see in total? Due to the special structure of the sunflower field, the number of plots that are adjacent to exactly one plot does not exceed $20$.

The first line contains two positive integers $n, c$, denoting the number of plots and the number of colors. The second line contains $n$ integers between $0$ and $c-1$, separated by spaces, where the $i$-th integer is the clothing color of the fan on the $i$-th plot. The next $n-1$ lines each contain two positive integers $u, v$, indicating that there is an edge connecting plot $u$ and plot $v$.

Output a single line with one integer, denoting the answer.

Constraints - For $15\%$ of the testdata, $n \le 2 \times 10^3$. - For another $5\%$ of the testdata, every plot is adjacent to at most two plots. - For another $5\%$ of the testdata, except for one plot that is adjacent to three plots, every other plot is adjacent to at most two plots. - For another $5\%$ of the testdata, except for two plots that are adjacent to three plots, every other plot is adjacent to at most two plots. - For $100\%$ of the testdata, $1 \le n \le 10^5$, $1 \le c \le 10$, $1 \le u, v \le n$. Translated by ChatGPT 5