题目链接：http://livearchive.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3003
———————————————————————————————————————
题目描述：
每个人都有且仅有一个上司，有且仅有一个人没有上司。（树形结构）
每个人都必须站在其上司后面，排成一队，有多少种站队方法。
———————————————————————————————————————
题目思路：
这题算是树型dp题吧。
我用的多叉转二叉实现的。
dp[i] 表示 到第i个节点共有多少个组合数。
dp[i] = c(1+i.son.num+i.bro.num , 1+i.son.num)* dp[i.son] *dp[i.bro]
————————————————————————————————————————
题目细节：
1、使用 long long int 型时一定要注意。
dp[cur] = (((c[tree[cur].val][nson+1]*max(dp[bro],1))%mod)*max(dp[son],1))%mod;
这句一开始我直接将他们相乘了，一直wa：
dp[cur] = (c[tree[cur].val][nson+1]*max(dp[bro],1)*max(dp[son],1))%mod;
也就是说，当中间结果有加或者乘的时候，一定要考虑清楚是否会在中间过程出现溢出！！
2、对于下面这个例子：(随便编的)
int dp[maxn];
long long int ans[maxn];
ans[i] = dp[j]*dp[j]
可能得到错误的结果，很明显，int *int仍然是int，会直接溢出，再把溢出的结果赋给ans。尽管ans是longlongint，仍然会得到溢出的答案
故要在前面乘上1ll，强制类型转换。
ans[i] = 1ll*dp[j]*dp[j]
3、多叉转二叉的时候，对于本题，可用如下代码，不需要搜到bro的最末端，在某些情况下可以大大节约时间。
next = tree[a].son;
tree[b].bro = next;
tree[next].fat = b;
tree[a].son = b;
原来的代码：
next = tree[a].son;
while(tree[next].bro!=n+1) next = tree[next].bro;
tree[next].bro = b; tree[b].fat = next;
4、其实类似于本题这种可以直接用vector做，省去很多麻烦，代码下（by hust_ghost）
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#define INF 1005
#define MOD 1000000007
using namespace std;
vector <int> vec[INF];
long long F[INF],D[INF][INF];
int Num[INF];
bool vis[INF];
void Tree_DP(int n)
{
int j,t,m,siz=vec[n].size(); Num[n]=F[n]=1;
for (j=0;j<siz;j++)
Tree_DP(t=vec[n][j]),Num[n]+=Num[t];
for (m=Num[n]-1,j=0;j<siz;j++)
F[n]=(F[n]*D[m][Num[t=vec[n][j]]])%MOD,
F[n]=(F[n]*F[t])%MOD,m-=Num[t];
}
int main()
{
int i,j,n,h,t,x,y;
for (D[0][0]=i=1;i<=INF-5;i++)
for (j=0;j<=i;j++)
D[i][j]=(D[i-1][j-1]+D[i-1][j])%MOD;
for (h=scanf("%d",&t);h<=t;h++)
{
memset(vis,true,sizeof(vis));
for (i=scanf("%d",&n);i<n;i++)
scanf("%d%d",&x,&y),vec[x].push_back(y),vis[y]=0;
for (i=1;i<=n;i++)
if (vis[i])
Tree_DP(i),printf("Case %d: %lld\n",h,F[i]);
for (i=1;i<=n;i++)
vec[i].clear();
}
return 0;
}
5、其实上例中c数组生成的方式并不好，c[i][j] 时会用到 c[i-1][j] ，意味着用到 c(i,j) (i<j) 的情况，这个是没有求过的。
也可能会出现 下标小于0的情况。若c数组的初值不为0，会产生很多意想不到的错误。所以将两个边界单独赋值，就会避免这类问题的发生。代码见下面。
——————————————————————————————————————————
源代码：
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <math.h>
using namespace std;
#define maxn 1010
#define INF 1000000000
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)>(b)?(b):(a))
#define mod 1000000007
long long int dp[maxn];
int n = 1;
long long int c[maxn][maxn];
struct tree_node
{
int fat;
int son;
int bro;
int val;
}tree[maxn];
void Cfun()
{
int i = 0,j = 0;
c[0][0] = 1;
for(i = 1;i<maxn;i++)
{
c[i][0] = c[i][i] = 1;
for(j = 1;j<=i-1;j++)
c[i][j] = (c[i-1][j-1]+c[i-1][j])%mod;
}
}
void tree_dp(int cur)
{
int bro = tree[cur].bro, son = tree[cur].son;
int nbro = 0,nson = 0;
if(bro == n+1 && son == n+1)
{
dp[cur] = 1;
tree[cur].val = 1;
return;
}
if(bro != n+1)
{
if(dp[bro] == -1)
tree_dp(bro);
nbro = tree[bro].val;
}
if(son != n+1)
{
if(dp[son] == -1)
tree_dp(son);
nson = tree[son].val;
}
tree[cur].val = nbro+nson+1;
dp[cur] = (((c[tree[cur].val][nson+1]*max(dp[bro],1))%mod)*max(dp[son],1))%mod;
}
int main()
{
//freopen("in.in","r",stdin);
//freopen("out.txt","w",stdout);
int k = 0,t = 0,i = 0;
Cfun();
scanf("%d",&t);
for(k = 1;k<=t;k++)
{
int a = 0,b = 0;
printf("Case %d: ",k);
scanf("%d",&n);
for(i = 1;i<=n;i++)
{
tree[i].fat = n+1;
tree[i].son = n+1;
tree[i].bro = n+1;
tree[i].val = 0;
}
memset(dp,-1,sizeof(dp));
for(i = 1;i<n;i++)
{
int next = 0;
scanf("%d%d",&a,&b);
tree[b].fat = a;
if(tree[a].son == n+1)
tree[a].son = b;
else
{
next = tree[a].son;
tree[b].bro = next;
tree[next].fat = b;
tree[a].son = b;
}
}
int f = 0;
for(i = 1;i<=n;i++)
if(tree[i].fat == n+1)
{
f = i;
break;
}
tree_dp(f);
printf("%lld\n",dp[f]);
}
return 0;
}