SRM570 - div2 - hard - 1000

組み合わせの数を求める問題

A社はケーブル持ってて
B社はケーブル持ってないので

B社がなんとかなる組み合わせ（ケーブルがつながってる組み合わせ）
の数を数える

#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<cmath>
#include<cstdio>
using namespace std;




class CentaurCompanyDiv2{
private:
	bool conect[60][60];
	long long dp[60];
	int N;
	bool vis[60];
	vector<int> sort;
public:
	long long dfs(int x){
		vis[x]=1;
		if(dp[x]!=-1){
			return dp[x];
		}
		long long res=1;
		for(int i=0;i<N;i++){
			if(vis[i]==0 && conect[x][i]==1){
				res*=(dfs(i)+1);
				if(res==0){
					cout<<"hogehoge"<<x<<i<<endl;
				}
			}
		}
		if(res==0){
			cout<<"hogee"<<endl;
		}
		dp[x]=res;
		
		cout<<x<<" "<<dp[x]<<endl;
		return res;
	}
	long long count(vector <int> a, vector <int> b){
		long long ans=1;
		for(int i=0;i<60;i++){
			dp[i]=-1;
			for(int j=0;j<60;j++){
				conect[i][j]=0;
			}
		}
		N=a.size()+1;
		for(int i=0;i<N-1;i++){
			conect[a[i]-1][b[i]-1]=1;
			conect[b[i]-1][a[i]-1]=1;
		}
		for(int i=0;i<N;i++){
			vis[i]=0;
		}
		dfs(0);
		for(int i=0;i<N;i++){
			ans+=dp[i];
		}
		return ans;
	}
};

ケーブル接続が木になっている
（木:ループがないグラフ）

各ノード毎にdpを行う
木dpってのになるっぽい

各ノード以下の木でできる組み合わせの数を保持させる
（枝の長さ＊枝の長さ）＊枝の長さ・・・・
みたいな感じ

深さ優先探索しながらDPして
dpで保持した値を全部足す＋［B社がなにも持ってないパターンの1］
が答え