Submission #1437809

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define MOD 1000000007
vector<int> G[222];
int n;
int dp[222][222];
int dp2[222][222];
int r[222];
int dp3[222][222][222];


int dfs2(int i,int j,int k){
  if(~dp3[i][j][k]) return dp3[i][j][k];
  if(i+j+k==0) return 1;
  int res=0;
  if(i>0&&j>0&&k>0) (res+=dfs2(i-1,j-1,k-1))%=MOD;
  if(i>0&&k>0) (res+=dfs2(i-1,j,k-1))%=MOD;
  if(j>0&&k>0) (res+=dfs2(i,j-1,k-1))%=MOD;
  return dp3[i][j][k]=res;
}

void calc(int v){
  memset(dp,0,sizeof(dp));
  dp[0][0]=1;
  for(int i=0;i<(int)G[v].size();i++){
    for(int j=0;j<=n;j++){
      for(int k=0;k<=n;k++){
	if(j+k>n) continue;
	for(int l=max(j,k);l<=j+k;l++){
	  (dp[i+1][l]+=(dp[i][j]*dp2[G[v][i]][k])%MOD*dfs2(j,k,l))%=MOD;
	}
      }
    }
  }
  /*//
  for(int i=0;i<=(int)G[v].size();i++)
    for(int j=0;j<=n;j++)
      cout<<v<<" "<<i<<" "<<j<<":"<<dp[i][j]<<endl;
  //*/
}

void dfs(int v){
  for(int u:G[v]) dfs(u);
  memset(dp2[v],0,sizeof(dp2[v]));
  calc(v);
  for(int i=0;i<=n;i++)
    dp2[v][i+1]=dp[G[v].size()][i];
}
signed main(){
  cin>>n;
  memset(r,0,sizeof(r));
  for(int i=0;i<n-1;i++){
    int a,b;
    cin>>a>>b;
    G[a].push_back(b);
    r[b]=1;
  }
  memset(dp3,-1,sizeof(dp3));
  int idx;
  for(int i=0;i<n;i++)
    if(!r[i]) dfs(i),idx=i;
  int ans=0;
  for(int i=0;i<=n;i++)
    (ans+=dp2[idx][i])%=MOD;
  cout<<ans<<endl;
  return 0;
}

Submission Info

Judge Result