fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. const int MAXN = 100000 + 10;
  4. const int MOD = (int)(1e9) + 7;
  5. vector<int> adj[MAXN];
  6. int fac[MAXN], rev[MAXN], f[MAXN], subtree[MAXN];
  7. int n;
  8. int power(int x, int k, int MOD) {
  9.     if (k == 0) return 1 % MOD;
  10.     long long t = power(x, k / 2, MOD);
  11.     t = (t * t) % MOD;
  12.     if (k % 2 == 1) t = (t * x) % MOD;
  13.     return t;
  14. }
  15. void init() {
  16.     int n = 100000;
  17.     fac[0] = 1;
  18.     for(int i = 1; i <= n; i++) fac[i] = (1LL * i * fac[i - 1]) % MOD;
  19.     for(int i = 0; i <= n; i++) rev[i] = power(fac[i], MOD - 2, MOD);
  20. }
  21. int combi(int k, int n) {
  22.     return (1LL * fac[n] * ((1LL * rev[k] * rev[n - k]) % MOD)) % MOD;
  23. }
  24. void DFS(int u, int par = -1) {
  25.     f[u] = 1; subtree[u] = 1;
  26.     for(int i = 0; i < adj[u].size(); i++) {
  27.         int v = adj[u][i];
  28.         if (v != par) {
  29.             DFS(v, u);
  30.             subtree[u] += subtree[v];
  31.         }
  32.     }
  33.     int s = subtree[u] - 1;
  34.     for(int i = 0; i < adj[u].size(); i++) {
  35.         int v = adj[u][i];
  36.         if (v != par) {
  37.             int x = (1LL * combi(subtree[v], s) * f[v]) % MOD;
  38.             f[u] = (1LL * f[u] * x) % MOD;
  39.             s -= subtree[v];
  40.         }
  41.     }
  42. }
  43. int main()
  44. {
  45.     init();
  46.     int test;
  47.     cin >> test;
  48.     while (test --) {
  49.         cin >> n;
  50.         for(int i = 1; i <= n; i++) adj[i].clear();
  51.         for(int i = 1; i <= n - 1; i++) {
  52.             int u, v;
  53.             cin >> u >> v;
  54.             adj[u].push_back(v); adj[v].push_back(u);
  55.         }
  56.         DFS(1);
  57.         cout << f[1] << endl;
  58.     }
  59. }
Success #stdin #stdout 0.2s 5968KB
comments (?)
stdin
copy 
3
3
1 2
2 3
3
1 2
1 3
4
1 2
2 3
1 4
stdout
copy 
1
2
3
https://ideone.com/eEyDYc
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!