记录编号	48241	评测结果	AAAAAAAAAA
题目名称	树的最大匹配	最终得分	100
用户昵称	王者自由	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2012-11-05 12:05:53	内存使用	3.19 MiB

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long int int64;
const int N = 1000 + 10;
int n;
vector<int> G[N];
int64 f[N][2], g[N][2];
int DP(int u) {
    int v; int64 t = 0, r;
    f[u][1] = 0, g[u][1] = 1;
    for(int i=0; i<G[u].size(); i++) {
        v = G[u][i];
        DP(v);
        f[u][1] += f[v][0];
        g[u][1] *= g[v][0];
    } f[u][0] = f[u][1];
    for(int i=0; i<G[u].size(); i++) {
        v = G[u][i];
        r = g[u][1] / g[v][0] * g[v][1];
        if(f[v][0] < f[v][1] + 1)
            f[u][0] = f[u][1] + 1, g[u][0] += r;
        if(f[u][0] == f[u][1] && f[v][0] == f[v][1] + 1)
            t += r;
    }
    if(f[u][0] == f[u][1])
        g[u][0] = g[u][1] + t;
}
int main() {
    freopen("treeb.in", "r", stdin);
    freopen("treeb.out", "w", stdout);
    scanf("%d", &n);
    bool l[N] = {0};
    int x, m, y, t;
    for(int i=0; i<n; i++) {
        scanf("%d %d", &x, &m);
        for(int i=0; i<m; i++) {
            scanf("%d", &y);
            G[x].push_back(y);
            l[y] = 1;
        }
    }
    for(int i=1; i<=n; i++)
        if(!l[i]) t = i;
    DP(t); // root
    printf("%lld\n%lld\n", f[t][0], g[t][0]);
    return 0;
}