Âm và Dương

Cho một cây gồm $N$ đỉnh được đánh số từ $1$ đến $N$, nối bởi $N-1$ cạnh. Mỗi cạnh có một loại: loại $0$ hoặc loại $1$.

Một đường đi cân bằng giữa hai đỉnh $u$ và $v$ ($u\ne v$) là đường đi trên cây từ $u$ đến $v$ thỏa mãn:

• Tổng số cạnh loại $0$ bằng tổng số cạnh loại $1$ trên toàn bộ đường đi.
• Tồn tại một đỉnh $r$ trên đường đi ($r\ne u$, $r\ne v$) sao cho đoạn từ $u$ đến $r$ cũng có số cạnh loại $0$ bằng số cạnh loại $1$.

Hãy đếm số lượng cặp đỉnh $(u,v)$ không phân biệt thứ tự có đường đi cân bằng.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $N$.
• $N-1$ dòng tiếp theo, mỗi dòng chứa ba số nguyên $a_i$, $b_i$, $t_i$ mô tả một cạnh nối đỉnh $a_i$ với đỉnh $b_i$ có loại $t_i$ ($t_i\in \{0,1\}$).

Dữ liệu ra

• In ra một số nguyên duy nhất: số cặp đỉnh có đường đi cân bằng.

Ràng buộc

• $1\le N\le 100000$
• $1\le a_i,b_i\le N$
• $t_i\in \{0,1\}$
• Đồ thị đầu vào là một cây.

Ví dụ