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;
}
Leave A Comment