Âm và Dương

Điểm: 1,00 (OI)

Giới hạn thời gian: 2.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

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 \neq 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 \neq u$ , $r \neq 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ò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}$ ).

Input	Output	Giải thích
7 1 2 0 3 1 1 2 4 0 5 2 0 6 3 1 5 7 1	1	Chỉ có cặp $(3, 7)$ thỏa mãn. Đường đi $3 \to 1 \to 2 \to 5 \to 7$ có $2$ cạnh loại $0$ và $2$ cạnh loại $1$ (cân bằng). Đỉnh nghỉ $r = 2$ : đoạn $3 \to 1 \to 2$ có $1$ cạnh loại $0$ và $1$ cạnh loại $1$ (cân bằng).
7 1 2 0 2 3 1 3 4 0 4 5 1 1 6 0 6 7 1	3	Ba cặp hợp lệ: $(1, 5)$ , $(3, 7)$ , $(5, 7)$ . Ví dụ cặp $(1, 5)$ : đường đi $1 \to 2 \to 3 \to 4 \to 5$ có $2$ cạnh loại $0$ và $2$ cạnh loại $1$ . Đỉnh nghỉ $r = 3$ : đoạn $1 \to 2 \to 3$ có $1$ cạnh mỗi loại.

Bình luận

Không có bình luận tại thời điểm này.