Submission #1260230

---

Source Code Expand

#include <unistd.h>
#include <vector>

const int mod = 1000000007;

typedef long long int ll;

std::vector<int> g[1000];

char ibuf[20000];
char *ibufe = ibuf-1;

void readall(){
  int k, t = 0;
  while((k=read(STDIN_FILENO, ibuf+t, sizeof(ibuf)-t))>0) t += k;
}

int read_uint(){
  int x=0;
  while(*(++ibufe) <'0');
  do {
    x *= 10;
    x += *ibufe-'0';
  } while(*(++ibufe) >='0');

  return x;
}

char buf[20];
char *bufe = buf;

void write_uintln(int x){
  int i;
  static char tmp[13];
  if(x==0){
    *bufe++ = '0';
    *bufe++ = '\n';
    return;
  }

  for(i=0; x; i++){
    tmp[i] = '0' + x % 10;
    x /= 10;
  }
  for(i--; i >= 0; i--){
    *bufe++ = tmp[i];
  }
  *bufe++ = '\n';
}

extern inline void writeall(){
  int k, t = 0;
  while((k=write(STDOUT_FILENO, buf+t, bufe-buf-t))>0) t += k;
}



struct prop {
  int num;
  int val;
};

int fact[1001];
int ifact[1001];
int iv[1001];

prop dp[1000];

int modpow(int n, int k){
  int r = 1;
  while(k){
    if(k&1) r = (ll) r * n % mod;
    k >>= 1;
    n = (ll) n * n % mod;
  }
  return r;
}

int inv(int x){
  return modpow(x, mod-2);
}

void dfs(int x, int p){
  dp[x].num=1;
  dp[x].val=1;
  for(auto c: g[x]){
    if(c != p){
      dfs(c, x);
      dp[x].val = (ll) dp[x].val * iv[dp[c].num] % mod * dp[c].val % mod;
      dp[x].num += dp[c].num;
    }
  }
}

void dfs2(int x, int p){
  int b = dp[p].num - dp[x].num;
  dp[x].val = (ll) dp[p].val * dp[x].num % mod * iv[b] % mod;
  dp[x].num += b;

  for(auto c: g[x]){
    if(c != p){
      dfs2(c, x);
    }
  }
}


int main(){
  int n, ans;

  fact[0] = 1;
  for(int i=1;i<=1000;i++){
    fact[i] = (ll) i * fact[i-1] % mod;
    iv[i] = inv(i);
  }
  ifact[1000] = inv(fact[1000]);
  for(int i=999;i>=0;i--){
    ifact[i] = (ll) (i+1) * ifact[i+1] % mod;
  }

  readall();
  n = read_uint();
  for(int i=0;i<n-1;i++){
    int a, b;
    a = read_uint();
    b = read_uint();
    g[a-1].push_back(b-1);
    g[b-1].push_back(a-1);
  }

  dfs(0, -1);
  iv[0] = iv[dp[0].num];
  dfs2(0, 0);

  ans = 0;
  for(int i=0;i<n;i++){
    ans = (ans + (ll) dp[i].val * fact[dp[i].num-1]) % mod;
  }

  write_uintln((int) ((ll) ans*ifact[2]%mod));

  writeall();

  return 0;
}

Submission Info

Judge Result