记录编号	541196	评测结果	AAAAAAAAAA
题目名称	树的最大匹配	最终得分	100
用户昵称	瑆の時間~無盡輪迴·林蔭	是否通过	通过
代码语言	C++	运行时间	0.035 s
提交时间	2019-09-06 12:06:31	内存使用	13.71 MiB

#include<iostream>
#include<cstdio>
#include<vector>
#define int long long int
using namespace std;
int dp[1001][2];
int g[1001][2];
int n,m,a1,root;
bool rd[1001];
vector<int> b[1001];
void DFS(int x,int fa)
{
	dp[x][0]=0;
	dp[x][1]=0;
	g[x][0]=1;
	g[x][1]=1;
	int mxf=0,sum=0;
	for(int i=0;i<b[x].size();i++)
	{
		int to=b[x][i];
		DFS(to,x);
		//dp[x][1]=max(dp[x][1],dp[to][0]-max(dp[to][0],dp[to][1])+1+dp[x][0]);
		if(dp[x][1])
		{
			dp[x][1]+=dp[to][1];
			if(dp[to][0]!=dp[to][1])
			{
				g[x][1]*=g[to][1];
			}
			else
			{
				g[x][1]*=g[to][0]+g[to][1];
			}
		}
		if(dp[x][0]+dp[to][0]+1>dp[x][1])
		{
			dp[x][1]=dp[x][0]+dp[to][0]+1;
			g[x][1]=g[x][0]*g[to][0];
		}
		else
		if(dp[x][0]+dp[to][0]+1==dp[x][1])
			g[x][1]+=g[x][0]*g[to][0];
		dp[x][0]+=dp[to][1];
		//dp[x][0]=max(dp[x][0],dp[x][0]+max(dp[to][0],dp[to][1]));
		 if(dp[to][0]!=dp[to][1]) 
		 	g[x][0]*=g[to][1];
        else
		 	g[x][0]*=g[to][0]+g[to][1];
	}
	if(!dp[x][1])
		g[x][1]=0;
} 
signed main()
{
	freopen("treeb.in","r",stdin);
	freopen("treeb.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		int ke;
		scanf("%d",&ke);
		scanf("%d",&m);
		for(int j=1;j<=m;j++)
		{
			scanf("%d",&a1);
			rd[a1]++;
			b[ke].push_back(a1);
		}
	}
	for(int i=1;i<=n;i++)
	{
		if(rd[i]==0)
		{
			root=i;
			break;
		}
	}
	DFS(root,0);
	cout<<dp[root][1]<<endl;
	if(dp[root][0]!=dp[root][1])
	{
		cout<<g[root][1];
	}
	else
	cout<<g[root][1]+g[root][0];
	return 0;
}