Đường đẹp

Có $N$ thành phố trong một đất nước được kết nối bằng $N-1$ con đường hai chiều, sao cho từ một thành phố bất kỳ có thể đi đến mọi thành phố khác (hệ thống đường tạo thành một cây). Một số thành phố là thành phố loại $1$, một số là loại $2$ và một số chưa được xếp loại. Đất nước được đảm bảo có ít nhất một thành phố loại $1$ và ít nhất một thành phố loại $2$.

Bạn chọn một con đường và loại bỏ nó ra khỏi hệ thống đường đi, khiến đất nước bị chia thành hai phần. Đó là một con đường đẹp nếu sau khi loại bỏ, không có phần nào chứa đồng thời cả thành phố loại $1$ và thành phố loại $2$. Một phần chỉ gồm các thành phố chưa được xếp loại vẫn được chấp nhận.

Yêu cầu: Hãy tính số lượng những con đường đẹp.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $N$ ($3\le N\le 3·{10}^5$), số thành phố. Các thành phố được đánh số từ $1$ đến $N$.
• Dòng thứ hai chứa $N$ số nguyên $a_1,a_2,\dots ,a_N$ ($0\le a_i\le 2$) là loại của các thành phố, trong đó:
  • $a_i=1$ nghĩa là thành phố $i$ là thành phố loại $1$;
  • $a_i=2$ nghĩa là thành phố $i$ là thành phố loại $2$;
  • $a_i=0$ nghĩa là thành phố $i$ chưa được xếp loại.
• Dòng thứ $i$ trong $N-1$ dòng tiếp theo chứa hai số nguyên $v_i,u_i$ ($1\le v_i,u_i\le N$) mô tả con đường nối hai thành phố $v_i$ và $u_i$. Các con đường tạo thành một cây.

Dữ liệu ra

In ra một số nguyên duy nhất là số lượng con đường đẹp.

Ràng buộc

• $3\le N\le 3·{10}^5$.
• $0\le a_i\le 2$; có ít nhất một $a_i=1$ và ít nhất một $a_i=2$.
• $1\le v_i,u_i\le N$; $N-1$ con đường tạo thành một cây.

Ví dụ