题目链接：uva 1436 - Counting heaps

题目大意：给出一个树的形状，现在为这棵树标号，保证根节点的标号值比子节点的标号值大，问有多少种标号树。

解题思路：和村名排队的思路是一只的uva11174,最后问题只和树德结构有直接关系，f(root)=(s(root)?1)!(s(1)?s(2)???s(n)

但是给定的取模数不是质数，所以不能用逆元做，只能将分子分母分别拆分成质因子，然后对质因子进制约分。因为最后的答案一定是正整数，所以对于每个质因子，分子分解出的因子个数一定大于等于分母分解出的，最后约分肯定剩下的是分子，再用快速幂求解。

剪枝，因为分解质因子的次数非常多，所以需要对分解函数剪枝，当u是质数时，可以直接终止返回。

#include 
   
     #include 
    
      #include 
     
       using namespace std; const int N = 500005; typedef long long ll; int P = 0, prime[N], ispri[N]; int n, f[N], vis[N], cnt[N]; ll mod; void getPrime (int N) { memset(ispri, 0, sizeof(ispri)); for (int i = 2; i < N; i++) { if (ispri[i]) continue; prime[P++] = i; for (int j = 2 * i; j < N; j += i) ispri[j] = 1; } } void getNode () { memset(cnt, 0, sizeof(cnt)); queue
      
        que; for (int i = 1; i <= n; i++) if (vis[i] == 0) que.push(i); while (!que.empty()) { int u = que.front(); que.pop(); cnt[u]++; int v = f[u]; cnt[v] += cnt[u]; vis[v]--; if (vis[v] == 0) que.push(v); } } void init () { memset(vis, 0, sizeof(vis)); scanf("%d%lld", &n, &mod); f[1] = 0; for (int i = 2; i <= n; i++) { scanf("%d", &f[i]); vis[f[i]]++; } getNode(); memset(vis, 0, sizeof(vis)); for (int i = 1; i <= n; i++) vis[cnt[i]]++; } ll power (ll x, ll m) { ll ans = 1; while (m) { if (m&1) ans = ans * x % mod; x = x * x % mod; m /= 2; } return ans; } void cal (int u, int v) { for (int i = 0; i < P; i++) { int k = prime[i]; while (u % k == 0) { cnt[k] += v; u /= k; } if (ispri[u] == 0) { cnt[u] += v; return; } } } ll solve () { memset(cnt, 0, sizeof(cnt)); for (int i = 2; i <= n; i++) cal(i, 1); for (int i = 2; i <= n; i++) if (vis[i]) cal(i, -vis[i]); ll ans = 1; for (int i = 0; i < P; i++) { ll u = prime[i]; if (cnt[u]) ans = (ans * power(u, cnt[u])) % mod; } return ans; } int main () { getPrime(N); int cas; scanf("%d", &cas); while (cas--) { init(); printf("%lld\n", solve()); } return 0; }