STONE1 - Rải sỏi
Giới hạn- Thời gian: 0.206s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Xét trò chơi rải sỏi với một người chơi như sau:
Cho cây T và một đống sỏi gồm K viên. Ở mỗi bước người ta lấy 1 viên sỏi từ đống sỏi và đặt vào một nút lá tuỳ ý. Nếu nút p có r nút lá và tất cả các nút lá đều đã có sỏi thì người ta gom tất cả các viên sỏi ở các nút lá lại, đặt 1 viên ở nút p, xoá các nút lá và trả r - 1 viên sỏi còn lại vào đống sỏi.
Trò chơi kết thúc khi đã đặt được 1 viên sỏi vào nút gốc
Yêu cầu: cho cây T, xác định số viên sỏi tối thiểu cần có để trò chơi có thể kết thúc. Cây có n nút (N <= 400), nút gốc được đánh số 1.
Input
- Dòng đầu: số n.
- Một số dòng tiếp theo, mỗi dòng có dạng: i m i1 i2 ... im. Trong đó m là số nút con của nút i; i1, i2, ..., im: các nút con của nút i.
Output
Số lượng viên sỏi ít nhất cần có.
Example
Input 7 1 2 2 3 2 2 5 4 3 2 6 7 Output 3
- Người up: dtmp