Cấu trúc dữ liệu cây là một trong những cấu trúc dữ liệu được sử dụng hiệu quả nhất trong ngành khoa học máy tính. Ta cho một cây nhị phân được đánh gốc, và n đỉnh. Các đỉnh được đánh số từ 1 tới n và đỉnh 1 là gốc. Nhiệm vụ của bạn là loại bỏ những nút lá để cây trở nên cân bằng mạnh, nghĩa là tất cả những cây con của nó cũng cân bằng. Một cây nhị phân có gốc được gọi là cân bàng nếu độ sâu của cây con trái và cây con bên phải có sự chênh lệch tối đa là 1. Việc loại bỏ đỉnh lá có thể khiển cho đỉnh cha của nó trở thành một lá. Như hình minh họa, cây trở nên cân bằng mạnh sau khi tất cả ba đỉnh 4, 5, 10 được loại bỏ, và đây là số lượng đỉnh ít nhất có thể loại bỏ để cây trở nên cân bằng mạnh.

Dữ liệu vào:

+ Dòng đầu tiên gồm số nguyên \(n(1 \leq n \leq {2.10}^{5})\) cho biết số đỉnh trong cây.

+ \(n - 1\) dòng tiếp theo mỗi dòng gồm hai số nguyên \(u\) và \(v\) \((1 \leq u,v \leq n,\ u
eq v)\) biểu thị một cạnh nối giữa đỉnh \(u\) và \(v\). Đảm bảo rằng các cạnh đã cho tạo thành một cây nhị phân hợp lệ với đỉnh 1 là gốc. Tuy nhiên các cạnh có thể xuất hiện theo bất kỳ thứ tự nào và vô hướng

Kết quả:

+ Một số nguyên cho biết số lượng các đỉnh lá nhỏ nhất ta cần loại bỏ để cây trở nên cân bằng mạnh.

Ví dụ:

Ràng buộc:

+ Có 30% số test có \(n \leq 100\)

+ Có 20% số test khác có \(n \leq 2000\)

+ Có 50% số test còn lại không có ràng buộc nào thêm