635
tc SRM 570 div2 1000 CentaurCompanyDiv2
题意很简单，就是给一棵树，问从中间取出成块划分有多少种方法。
用dfs即可，dfs(i)代表i可划分的情况，所以上一级就是ans*(dfs(i)+1)因为可以取也可以不取，所以情况数加1.
class CentaurCompanyDiv2 {
public:
long long count(vector <int>, vector <int>);
};
vector<int> mm[55];
bool vis[55];
long long cnt;
long long dfs(int v)
{
int u,i;
long long ans=1;
vis[v]=1;
for(i=0;i<mm[v].size();i++)
{
u=mm[v][i];
if(!vis[u])ans*=(dfs(u)+1);//可取也可不取
}
cnt+=ans;
return ans;
}
long long CentaurCompanyDiv2::count(vector <int> a, vector <int> b) {
int n=a.size()+1,i;
for(i=1;i<=n;i++)
{
mm[i].clear();
vis[i]=0;
}
for(i=0;i<a.size();i++)
{
mm[a[i]].push_back(b[i]);
mm[b[i]].push_back(a[i]);
}
cnt=0;
dfs(1);
return cnt+1;//全都不取
}
最后更新：2017-04-04 07:03:48