题目链接：uva 1436 - Counting heaps

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

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

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

剪枝。由于分解质因子的次数许多。所以须要对分解函数剪枝。当u是质数时，能够直接终止返回。

#include <cstdio>

#include <cstring>

#include <queue>

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<int> 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;

}