题目大概是说给一棵树的n个结点从1到n编号，要求每个结点的编号大于其父结点，问有多少种编号方式。
想了挺久的，感觉有点眉目，最后画了下样例YY出解法：
- 首先求出以每个结点为根的子树大小，记为size[u]，这个DFS一遍就可以求出来；
- 接下来，dp[u]表示给以u为根的子树size[u]个编号有几种编号方案 ；
- 然后考虑转移方程：
- 比如一个结点u有3个儿子v1,v2,v3，那么u子树有size[u]个编号，编号最小的就属于u，剩下size[u]-1分配给u的三个子树，分配方式就有：
C(size[u]-1,size[v1])*C(size[u]-1-size[v1],size[v2])*C(size[u]-1-size[v1]-size[v2],size[v3]) 种
- 而v1、v2和v3子树对它们被分配的编号又分别有dp[v1]、dp[v2]和dp[v3]种编号方案，因此u子树的size[u]个编号总共的编号方式即dp[u]是：
dp[u] = dp[v1]*dp[v2]*dp[v3]*C(size[u]-1,size[v1])*C(size[u]-1-size[v1],size[v2])*C(size[u]-1-size[v1]-size[v2],size[v3])
于是就是这样用DP求解的。另外C(n,m)可以利用组合数的递推式C(n,m)=C(n-1,m)+C(n-1,m-1)预处理出来。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct Edge{
int v,next;
}edge[];
int NE,head[];
void addEdge(int u,int v){
edge[NE].v=v; edge[NE].next=head[u]; head[u]=NE++;
}
int n,size[];
long long C[][],d[];
int getSize(int u){
if(size[u]) return size[u];
int res=;
for(int i=head[u]; i!=-; i=edge[i].next){
int v=edge[i].v;
res+=getSize(v);
}
return size[u]=res;
}
long long dfs(int u){
if(d[u]) return d[u];
long long res=;
int cnt=size[u]-;
for(int i=head[u]; i!=-; i=edge[i].next){
int v=edge[i].v;
res*=(dfs(v)*C[cnt][size[v]])%;
res%=;
cnt-=size[v];
}
return res;
}
int main(){
for(int i=; i<; ++i) C[i][]=;
for(int i=; i<; ++i){
for(int j=; j<=i; ++j) C[i][j]=(C[i-][j]+C[i-][j-])%;
}
int t,a,b;
scanf("%d",&t);
for(int cse=; cse<=t; ++cse){
NE=;
memset(head,-,sizeof(head));
bool uroot[]={};
scanf("%d",&n);
for(int i=; i<n; ++i){
scanf("%d%d",&a,&b);
addEdge(a,b);
uroot[b]=;
}
int root;
for(int i=; i<=n; ++i){
if(!uroot[i]){
root=i;
break;
}
}
memset(size,,sizeof(size));
getSize(root);
memset(d,,sizeof(d));
printf("Case %d: %lld\n",cse,dfs(root));
}
return ;
}