记录编号	21021	评测结果	AAAAAAAAAA
题目名称	树的最大匹配	最终得分	100
用户昵称	.Xmz	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2010-11-02 16:36:58	内存使用	3.26 MiB

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <cstring>

using namespace std;

int n,a,b;
int y[1001];
long long f[1001][2],g[1001][2];

struct edge
{
	int t;
	edge *next;
}E[10001],*V[1001];
int eh;

inline void addedge(int a,int b)
{
	E[++eh].next=V[a];  V[a]=E+eh;  V[a]->t=b;
}

void dp(int u)
{
	g[u][1]=1;
	for (edge *e=V[u];e;e=e->next)
	{
		dp(e->t);
		f[u][1]+=f[e->t][0];
		g[u][1]*=g[e->t][0];
	}
	long long t=0;
	f[u][0]=f[u][1];
	for (edge *e=V[u];e;e=e->next)
	{
		if (f[e->t][1]+1>f[e->t][0]) f[u][0]=f[u][1]+1,g[u][0]+=g[u][1]/g[e->t][0]*g[e->t][1];
		if (f[u][0]==f[u][1] && f[e->t][1]+1==f[e->t][0]) t+=g[u][1]/g[e->t][0]*g[e->t][1];
	}
	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);
	int t;
	for (int i=1;i<=n;i++)
	{
		scanf("%d%d",&a,&t);
		for (int i=1;i<=t;i++)
		{
			scanf("%d",&b);
			addedge(a,b);y[b]=true;
		}
	}
	int i;
	for (i=1;i<=n;i++) if (!y[i]) {dp(i);break;}
	printf("%lld\n%lld\n",f[i][0],g[i][0]);
	return 0;
}