1000:CentaurCompany

哎，好久没写Topcoder了，然后现在来补作业。。。

题意：

给你一棵树，询问其中有多少种连通块（可以不包含任何元素）。。。

分析:

大力搞一搞树形dp就好了，我们考虑dp[i]表示以i为根的子树中包含根的连通块数量。。。

代码:

 

LL way[55][55],n;
LL dp[55],ans;
void find(int now,int fa)
{
	vectorflag;
	flag.clear();
	for(int i=1;i<=n;i++)
		if(way[now][i]&&i!=fa)
		{
			find(i,now);
			flag.push_back(dp[i]);
		}
	if(flag.size()==0)
		dp[now]=1;
	else
	{
		dp[now]=flag[0]+1;
		for(int i=1;i<flag.size();i++)
			dp[now]*=flag[i]+1;
	}
	ans+=dp[now];
}
long long CentaurCompanyDiv2::count(vector  a, vector  b)
{
	ans=0;
	n=a.size()+1;
	memset(dp,0,sizeof(dp));
    memset(way,0,sizeof(way));
    for(int i=0;i<n-1;i++)
    	way[a[i]][b[i]]=way[b[i]][a[i]]=1;
    find(1,0);
    return ans+1;
}