| 比赛场次 | 179 |
|---|---|
| 比赛名称 | 20101101 |
| 比赛状态 | 已结束比赛成绩 |
| 开始时间 | 2012-11-05 08:15:00 |
| 结束时间 | 2012-11-05 12:00:00 |
| 开放分组 | 全部用户 |
| 注释介绍 |
| 题目名称 | 树的最大匹配 |
|---|---|
| 输入输出 | treeb.in/out |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 128 MiB |
| 测试点数 | 10 简单对比 |
| 用户 | 结果 | 时间 | 内存 | 得分 |
|---|---|---|---|---|
 kaaala |
AAAAAAAAAA | 0.004 s | 3.18 MiB | 100 |
 王者自由 |
AAAAAAAAAA | 0.005 s | 3.19 MiB | 100 |
 Truth.Cirno |
AWWWWWWWWW | 0.020 s | 7.07 MiB | 10 |
 亟隐 |
WWWWWWWWWW | 0.004 s | 0.21 MiB | 0 |
 苏轼 |
WWWWWWWWWW | 0.005 s | 3.28 MiB | 0 |
【题目描述】
给一棵树，你可以匹配有边相连的两个点，问这棵树的最大匹配是多少，并且计算出有多少种最大匹配
【输入格式】
第一行一个数 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