比赛 |
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);
}