Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

STONE1 - Rải sỏi

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

Được gửi lên bởi:Nguyen Dinh Tu
Ngày:2006-10-11
Thời gian chạy:0.206s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:BF C CSHARP CPP LISP sbcl LISP clisp HASK JAVA OCAML PAS-GPC PAS-FPC PERL PHP PYTHON

hide comments
2019-08-15 23:31:43
một bài quy hoạch động trên cây cơ bản . code cho bạn nào cần tham khảo : https://ideone.com/k1k2oT .
2019-08-15 23:31:43
một bài quy hoạch động trên cây cơ bản . code cho bạn nào cần tham khảo : https://ideone.com/k1k2oT .
2018-07-10 02:56:57
Dành cho ai cần :v
http://bit.ly/2Fu2yTh

Last edit: 2019-01-12 01:46:22
2018-04-04 15:56:28
easy
2017-12-27 15:36:57
ledacthuongvq
2017-12-08 03:41:43
nhật hào sạch
2017-09-22 15:41:04


THAM KHẢO THUẬT TOÁN VÀ CODE TẠI:

http://yeulaptrinh.pw/1234/stone1-spoj/


2013-09-16 13:04:14 a;slkfjasl;fkj
bài hay :)
2012-07-26 09:54:33 Thắng 20 cm
code ko cần debug vẫn AC,=))
2011-12-12 10:00:24 Normal Skills
bai` cui` pap'
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.