[HNOI2008]明明的烦恼 树的 prufer 编码
#include <cstdio>#include <cstdlib>#include <cstring>#define maxn 1000struct longint {int a[maxn];int & operator [](const int & b) {return a[b];}}ans, kk;void operator *=(longint & a, const int & b){int i;for (i = 1; i <= a[0]; ++ i) a[i] *= b;for (i = 1; i <= a[0]; ++ i)if (a[i] >= 10000) a[i + 1] += a[i] / 10000, a[i] %= 10000;if (a[a[0] + 1]) ++ a[0];}void print(longint & a){int i;printf("%d", a[a[0]]);for (i = a[0] - 1; i >= 1; -- i) printf("%04d", a[i]);puts("");}struct da {int s, t; da * n;} das[maxn * 30];da * edge[maxn + 5], * adj = das;int n, deg, rest, sum, tot;int pm[maxn + 5], num[maxn + 5];bool np[maxn + 5];void prepare(){int i, j, k;for (i = 2; i <= maxn; ++ i){if (! np[i]) pm[++ tot] = i;for (j = 1; j <= tot; ++ j){k = pm[j] * i;if (k > maxn) break; else np[k] = 1;if (i % pm[j] == 0) break;}}for (i = 1; i <= maxn; ++ i)for (j = 1; j <= tot; ++ j){k = i;if (pm[j] > i) break;if (i % pm[j]) continue; else k = i / pm[j];* (++ adj) = (da) {1, j, edge[i]}, edge[i] = adj;for (; k % pm[j] == 0; k /= pm[j]) ++ adj->s;}}int main(){freopen("1005.in", "r", stdin);freopen("1005.out", "w", stdout);int i, j; da * e;scanf("%d", & n), prepare();for (i = 1; i <= n; ++ i){scanf("%d", & deg);if (~ deg)for (sum += deg - 1, j = 1; j < deg; ++ j)for (e = edge[j]; e; e = e->n) num[e->t] -= e->s;else ++ rest;}for (i = n - 2; i > n - 2 - sum; -- i)for (e = edge[i]; e; e = e->n) num[e->t] += e->s;for (e = edge[rest]; e; e = e->n)num[e->t] += (n - 2 - sum) * e->s;ans[0] = ans[1] = 1;for (i = 1; i <= tot; ++ i)for (j = 1; j <= num[i]; ++ j) ans *= pm[i];print(ans);return 0;}