题目链接

题意：n个人排队，每个人b除CEO外都有一个监督人a，b必须排在a的后面，问有多少排队方案。

  思路: 这是一道树形dp和组合数学的题目,当时训练的时候公式推对了 ,但是写的时候想错了...

这道题我一看是n个点 n-1个边 又有上下级关系 所以我们就想到可以看成一个树,那么我们dp[i] 表示以i为根节点所能排队的方案数,

num[i]表示以i为根节点的字数一共有几个结点,那么我们在将两个点合并到上层的时候

有: C（num[i]+num[j],num[i]）*dp[i]*dp[j];

但是我们在合并的时候 考虑到会出现n叉树所以不能两两合并,那么我们就将其处理成每次一个子树和其父节点合并

转化成(C[num[u]-1][num[v]])*dp[u]%mod)*dp[v] u代表根节点 -1 去掉根节点

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2222;
const ll mod=1e9+7;
ll C[maxn][maxn];
int book[maxn];
ll dp[maxn],num[maxn];
vector<int>vt[maxn];
int t,n,a,b;
void init()
{C[1][0]=C[1][1]=C[0][0]=1;for(int i=1;i<maxn;i++){C[i][i]=C[i][0]=1;for(int j=1;j<i;j++)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;}return ;
}
void dfs(int u,int f)
{ 	int i,v;dp[u]=1;num[u]=1;for(i=0;i<vt[u].size();i++){ 	v=vt[u][i];if(v==f)continue;dfs(v,u);num[u]+=num[v];dp[u]=((C[num[u]-1][num[v]])*dp[u]%mod)*dp[v]%mod;	} return ;
}
int main()
{init();/*for(int i=1;i<=10;i++){for(int j=1;j<=i;j++)printf("%lld\n",C[i][j]);}*/cin>>t;int k=1;while(t--){for(int i=1;i<=n;i++)vt[i].clear();memset(dp,0,sizeof(dp));memset(num,0,sizeof(num));memset(book,0,sizeof(book));scanf("%d",& n);for(int i=1;i<n;i++){scanf("%d %d",& a,& b);vt[a].push_back(b);book[b]++;}for(int i=1;i<=n;i++){if(!book[i]){dfs(i,-1);printf("Case %d: ",k++);printf("%lld\n",dp[i]);break;}}}return 0;
}