#P1623. [CEOI2007] 树的匹配 Treasury

    ID: 667 远端评测题 500ms 32MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>动态规划dp高精度树形结构最大匹配2007

[CEOI2007] 树的匹配 Treasury

题目描述

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

输入格式

第一行一个整数 NN,表示有多少个结点。

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

输出格式

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

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

提示

1N1031\leq N\leq 10^3,其中 40%40\% 的数据答案不超过 10810^8