Cho một cây có đỉnh, gốc là đỉnh . Có truy vấn, mỗi truy vấn gồm một đỉnh và một số nguyên .
Để xử lý một truy vấn, bạn có thể xóa bất kỳ đỉnh nào từ cây theo bất kỳ thứ tự nào, số lượng xoá tuỳ ý, ngoại trừ đỉnh gốc và đỉnh . Khi một đỉnh bị xóa, các con của nó trở thành con của cha nó. Bạn cần xử lý truy vấn sao cho giá trị là lớn nhất có thể, trong đó:
là số con còn lại của đỉnh sau khi xử lý truy vấn.
là số đỉnh bạn đã xóa.
Yêu cầu: Với mỗi truy vấn, in ra giá trị lớn nhất mà bạn có thể đạt được.
Chú ý: Các truy vấn là độc lập (tức là các thay đổi bạn thực hiện với cây khi xử lý một truy vấn không ảnh hưởng đến cây ở các truy vấn khác).
Dữ liệu:
Dòng đầu: số nguyên ().
dòng tiếp theo: mỗi dòng chứa hai số — cạnh của cây.
Dòng tiếp theo: số nguyên .
dòng tiếp theo: mỗi dòng chứa hai số .
Kết quả: dòng, mỗi dòng là kết quả của truy vấn tương ứng.
Ví dụ:
Dữ liệu:
5
1 5
2 3
3 5
4 5
3
1 0
5 2
3 2
Kết quả:
2
2
1
Giải thích:
: xóa các đỉnh và , đỉnh còn lại con (các đỉnh , ), và điểm số là .
: Không xóa đỉnh nào, đỉnh còn lại con (các đỉnh , ), và điểm số là .
: Không xóa đỉnh nào, đỉnh có con (đỉnh ), điểm số là .
Giới hạn:
Subtask #1: 20% số điểm với cho mọi truy vấn.
Subtask #2: 20% số điểm với .
Subtask #3: 60% số điểm còn lại không có ràng buộc thêm.
