Một cây nhị phân được cho dưới dạng danh sách nút. Nút 0 là gốc. Mỗi nút có: con trái, con phải (chỉ số nút, hoặc −1 nếu không có) và một cờ "thuần" u∈{0,1} (1 nghĩa là mọi mẫu tại nút này cùng một lớp).
Quy tắc cắt tỉa (hậu cắt tỉa bottom-up): nếu một nút NỘI (có con) là thuần (u=1), ta biến nó thành lá bằng cách bỏ cả hai cây con. Áp dụng lặp cho tới khi không còn thay đổi.
Một nút ban đầu là lá nếu cả hai con đều −1. Sau khi cắt tỉa, hãy đếm tổng số LÁ của cây kết quả (tính từ gốc, chỉ các nút còn được giữ lại). In ra số lá (số nguyên, in dạng số thực 2 chữ số thập phân).
Lưu ý: một nút nội thuần khi bị cắt sẽ trở thành lá và toàn bộ cây con của nó không còn được đếm.
Dòng 1: số nút K. K dòng tiếp: mỗi dòng ba số nguyên: con trái, con phải, cờ thuần u.
1≤K≤100; cây hợp lệ, không chu trình, gốc là nút 0.
Một số thực: số lá sau cắt tỉa (làm tròn 2 chữ số).
Ví dụ:
Đầu vào:
3
1 2 0
-1 -1 1
-1 -1 1
Đầu ra:
2.00
Giải thích:
Đang tải editor...