记录编号	49278	评测结果	AAAAAAAAAA
题目名称	树的最大匹配	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2012-11-07 16:12:17	内存使用	0.36 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<vector>
using namespace std;
int n,m,number,tmp;
vector<int>con[1005];
long long q[1005][2]={0},w[1005][2]={0};
void dfs(int x);
int main()
{
	freopen ("treeb.in","r",stdin);
	freopen ("treeb.out","w",stdout);
	cin>>n;
	for (int i=0;i<n;i++)
	{
		cin>>m>>number;
		for (int j=0;j<number;j++)
		{
			cin>>tmp;
			con[m].push_back(tmp);
		}
	}
	dfs(1);
	if (q[1][1]>q[1][0])
	{
		cout<<q[1][1]<<endl<<w[1][1];
	}
	if (q[1][1]<q[1][0])
	{
		cout<<q[1][0]<<endl<<w[1][0];
	}
	if (q[1][0]==q[1][1])
	{
		cout<<q[1][1]<<endl<<w[1][0]+w[1][1];
	}
	return 0;
}
void dfs(int x)
{
	for (int i=0;i<con[x].size();i++)
	{
		dfs(con[x][i]);
	}
	long long temp=0,nnum=0,ttemp=1,nnumber=1;
	w[x][0]=1;
	for (int i=0;i<con[x].size();i++)
	{
		ttemp=w[con[x][i]][0];
		temp=q[con[x][i]][0]+1;
		for (int j=0;j<con[x].size();j++)
		{
			if (j!=i)
			{
				if (q[con[x][j]][1]<q[con[x][j]][0])
				{
					temp+=q[con[x][j]][0];
					ttemp*=w[con[x][j]][0];
				}
				if (q[con[x][j]][1]==q[con[x][j]][0])
				{
					temp+=q[con[x][j]][0];
					ttemp*=w[con[x][j]][1]+w[con[x][j]][0];
				}
				if (q[con[x][j]][1]>q[con[x][j]][0])
				{
					temp+=q[con[x][j]][1];
					ttemp*=w[con[x][j]][1];
				}
			}
		}
		if (q[con[x][i]][0]<q[con[x][i]][1])
		{
			nnum+=q[con[x][i]][1];
			nnumber*=w[con[x][i]][1];
		}
		if (q[con[x][i]][0]==q[con[x][i]][1])
		{
			nnum+=q[con[x][i]][1];
			nnumber*=w[con[x][i]][1]+w[con[x][i]][0];
		}
		if (q[con[x][i]][0]>q[con[x][i]][1])
		{
			nnum+=q[con[x][i]][0];
			nnumber*=w[con[x][i]][0];
		}
		if (temp==q[x][1])
		{
			w[x][1]+=ttemp;
		}
		if (temp>q[x][1])
		{
			q[x][1]=temp;
			w[x][1]=ttemp;
		}
	}
	if (nnum==q[x][0]&&nnum!=0)
		w[x][0]+=nnumber;
	if (nnum>q[x][0])
	{
		q[x][0]=nnum;
		w[x][0]=nnumber;
	}
}