树的最大匹配

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 treeb.in 输出文件 treeb.out

【题目描述】

给一棵树，你可以匹配有边相连的两个点，问这棵树的最大匹配是多少，并且计算出有多少种最大匹配

【输入格式】

第一行一个数 N ，表示有多少个结点。

接下来 N 行，每行第一个数，表示要描述的那个结点的编号。然后一个数 m ，表示这个结点有 m 个儿子，接下来 m 个数，表示它的 m 个儿子的编号。

【输出格式】

输出两行，第一行为最大匹配数，第二行输出最大匹配方案数。

【输入样例】

7
1 3 2 4 7
2 1 3
4 1 6
3 0
7 1 5
5 0
6 0

【输出样例】

3
4

【数据规模】

N<=1000, 其中 40% 的数据答案不超过 10^7