Anton gần đây đang đi dạo quanh Kaunas trong kỳ thi EJOI và phát hiện ra $N$ địa điểm nơi các thí sinh tụ tập. Các địa điểm được đánh số từ 0 đến $N-1$. Mỗi địa điểm được chiếm giữ bởi các thành viên của đúng một đội, và các đội được đánh số từ 0 đến $K-1$. Lưu ý rằng các thành viên của cùng một đội có thể chiếm giữ số địa điểm tùy ý. Một số đội có thể không chiếm địa điểm nào.

Các địa điểm được nối với nhau bằng $N-1$ con đường hai chiều sao cho giữa hai địa điểm bất kỳ có đúng một đường đi đơn, vì vậy chúng tạo thành một cây. Nhắc lại rằng đường đi đơn giữa hai địa điểm là một dãy các địa điểm phân biệt trong đó hai địa điểm liên tiếp bất kỳ được nối với nhau bằng một con đường. Độ dài của một đường đi là số con đường nó sử dụng, tức là số địa điểm nó đi qua trừ đi 1.

Anton muốn đi dạo dọc theo một đường đi đơn, thăm càng nhiều địa điểm càng tốt. Một đường đi đơn được gọi là thú vị nếu độ dài của nó là lớn nhất có thể trong số tất cả các đường đi đơn trên cây. Teamfulness của một đường đi là số đội khác nhau mà Anton gặp dọc theo nó.

Nhiệm vụ của bạn là tìm tổng teamfulness trên tất cả các đường đi thú vị khác nhau. Hai đường đi thú vị được coi là giống nhau khi và chỉ khi chúng đi qua đúng cùng một tập hợp các địa điểm (cụ thể, đi qua một đường đi theo hướng ngược lại không tạo ra một đường đi khác).

Chi tiết cài đặt

Bạn cần cài đặt hàm sau:

long long teamfulness(int N, int K, std::vector<int> a,
                      std::vector<int> u, std::vector<int> v)

• $N$: số địa điểm;
• $K$: số đội;
• $a$: một mảng gồm $N$ số nguyên, trong đó $a_i$ là đội chiếm giữ địa điểm $i$, với mọi $0 \le i < N$;
• $u, v$: hai mảng gồm $N-1$ số nguyên, trong đó $u_i$ và $v_i$ là hai địa điểm được nối bởi con đường thứ $i$, với mọi $0 \le i < N-1$.

Hàm này được gọi đúng một lần cho mỗi test và phải trả về tổng teamfulness trên tất cả các đường đi thú vị.

Giới hạn

• $3 \le N \le 10^6$
• $1 \le K < N$
• $0 \le a_i < K$ với mọi $0 \le i < N$
• $0 \le u_i, v_i < N$ với mọi $0 \le i < N-1$

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

21

Dữ liệu vào 2

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

Dữ liệu ra 2

4

Dữ liệu vào 3

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

Dữ liệu ra 3

11

Ghi chú 1

Độ dài tối đa của một đường đi đơn là 2 (2 con đường, 3 địa điểm), do đó các đường đi thú vị sẽ có độ dài 2. Có hai đường đi thú vị với teamfulness 3, bảy đường đi thú vị với teamfulness 2, và một đường đi thú vị với teamfulness 1, tổng cộng là 21.

Ghi chú 2

Các địa điểm và các con đường nối chúng được minh họa như sau (đội 0 được tô màu vàng):

Teamfulness của mọi đường đi đều là 1 vì chỉ có một đội (đội 0) có mặt tại mọi địa điểm. Có 4 đường đi thú vị (có độ dài 4), do đó tổng teamfulness trên tất cả các đường đi thú vị cũng là 4.

Ghi chú 3

Các địa điểm và các con đường nối chúng được minh họa như sau (đội 0 được tô màu vàng, đội 1 được tô màu xanh lá cây, đội 2 được tô màu đỏ):

Các đường đi thú vị có độ dài 3. Tổng cộng có bốn đường đi thú vị: ba đường có teamfulness 3, và một đường có teamfulness 2. Do đó, tổng teamfulness trên tất cả các đường đi thú vị là 11.

Nhiệm vụ con

Ví dụ

Định dạng dữ liệu vào như sau:

• dòng 1: hai số nguyên – giá trị của $N$ và $K$;
• dòng 2: $N$ số nguyên $a_0, a_1, \dots, a_{N-1}$, trong đó $a_i$ là đội chiếm giữ địa điểm $i$;
• dòng $3+i$: hai số nguyên $u$ và $v$ – hai địa điểm được nối bởi con đường thứ $i$.

Định dạng dữ liệu ra như sau:

• dòng 1: một số nguyên – giá trị trả về của lời gọi hàm.