比赛 20101101 评测结果 AWWWWWWWWW
题目名称 树的最大匹配 最终得分 10
用户昵称 Truth.Cirno 运行时间 0.020 s
代码语言 C++ 内存使用 7.07 MiB
提交时间 2012-11-05 11:44:36
显示代码纯文本
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

unsigned long long counter[2][1010];
int n,root,sonnum[1010],son[1010][1010],f[2][1010];
bool una[1010];

void fillit(int pos)
{
	int i,to,sum=0,add=0;
	unsigned long long add2=0;
	for (i=0;i<sonnum[pos];i++)
	{
		to=son[pos][i];
		fillit(to);
		sum+=f[0][to];
		add=max(add,f[1][to]-f[0][to]);
		counter[1][pos]+=counter[0][to];
	}
	for (i=0;i<sonnum[pos];i++)
	{
		to=son[pos][i];
		if (add==f[1][to]-f[0][to])
			add2+=counter[1][to]-counter[0][to];
	}
	f[0][pos]=sum+add;
	f[1][pos]=sum+1;
	counter[0][pos]=counter[1][pos]+add2;
	counter[1][pos]++;
}

int main(void)
{
	freopen("treeb.in","r",stdin);
	freopen("treeb.out","w",stdout);
	int i,j,code,m,temp;
	cin>>n;
	for (i=1;i<=n;i++)
	{
		cin>>code>>m;
		for (j=1;j<=m;j++)
		{
			cin>>temp;
			son[code][sonnum[code]++]=temp;
			una[temp]=true;
		}
	}
	for (i=1;i<=n;i++)
		if (!una[i])
		{
			root=i;
			break;
		}
	fillit(root);
	cout<<f[0][root]<<endl;
	cout<<counter[0][root]+1<<endl;
	return(0);
}