Lightoj 1382 - The Queue

http://lightoj.com/volume_showproblem.php?problem=1382

Problem analysis:

This is a rare problem i wrote about so far.  After much struggling we can actually see that this is nothing but a tree combination that means we can represent each permutation of queue as a tree where the root is the supervisor and each of the  employee under that supervisor is the the child of that root. that means in the queue no child can be before it's root. after building the tree the only question is how many ways are there to represent the queue using the tree where no child is before and root or root of root?

After much struggling and using different combinatorics rules we can see that there is no way without making the problem smaller (yeah i am talking about DP) and building the ultimate answer using those smaller results. So first these questions are important to answer??
1. What this root actually means of the tree??
2. How the childs are connected to the root?? By this I mean how to combine the results of the childs results to construct the roots result??
and finally
3. how to find the result of the childs??

Answers:
1. root means whatever i do later that is not my concern but right now this root must be in the position (the child or child of child is for later)  and  than go for the childs.

2. here for each root we can calculate how many positions available after fixing the position of the root and than we can also calculate how many positions are needed for a certain child(total number of that child including that child) so if our function is dp(int root) for each child we can just use

ncr(total_positions_available,positions_needed_for_child_i)*dp(i)

we can pre calculate the values of ncr and after constructing the tree we can easily calculate number of childs of each root. that we can use the DP function to find the answer.

Here goes the code.

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define MOD 1000000007
4. #define llu long long unsigned
5. vector<int>v[1005];
6. bool vis[1005];
7. llu chi[1005];
8. llu ncr[1005][1005];
9. llu dp[1005];
11. llu child(llu root){
12.     if(v[root].size() == 0) return chi[root] = 1;
13.     llu sum = 0;
14.     for(int i = 0; i <(int)v[root].size(); i++){
15.         sum += child(v[root][i]);
16.     }
17.     return chi[root] = 1+sum;
18. }
19. void NCR(){
20.     ncr[0][0] = 1;
21.     for(int i = 1; i <1005; i++){
22.         for(int j = 0; j <=i; j++){
23.             if(j == 0 || j == i) ncr[i][j] = 1;
24.             else ncr[i][j]= (ncr[i-1][j]+ncr[i-1][j-1])%MOD;
25.         }
26.     }
27.     /*
28.     for(int i = 0; i <10; i++){
29.         for(int j = 0; j <10; j++){
30.             printf("%d ", ncr[i][j]);
31.         }
32.         printf("\n");
33.     }
34.     */
35. }
36. llu DP(llu root){
37.     llu totalsize = chi[root]-1; // except himself
38.     llu ans = 1;
39.     for(int i = 0; i <(int)v[root].size(); i++){
40.         llu chld = v[root][i];
41.         llu chldsize = chi[chld];
42.         ans*=(ncr[totalsize][chldsize]*DP(chld))%MOD;
43.         ans%=MOD;
44.         totalsize-=chldsize;
45.     }
46.     return dp[root] = ans;
47. }
48. int main(){
49.     NCR();
50.     int ts;
51.     scanf("%d", &ts);
52.     for(int p = 1; p <=ts; p++){
53.     int n;
54.     scanf("%d", &n);
55.     memset(vis, false, sizeof(vis));
56.     for(int i = 1; i <=n; i++) v[i].clear();
57.     for(int i = 1; i <n; i++){
58.         int a, b;
59.         scanf("%d%d", &a, &b);
60.         v[a].push_back(b);
61.         vis[b] = true;
62.     }
63.     int mark;
64.     for(int i = 1; i <=n; i++){
65.         if(!vis[i]){mark = i;break;}
66.     }
67.     child(mark);
68.     printf("Case %d: %lld\n",p,  DP(mark));
69.     }
70.     return 0;
71. }