#301926 (C) No.758 VVVVV

• 問題: No.758 VVVVV
• ユーザー: akakimidori
• 提出日時: 2018-12-06 08:28:53
• 言語: C (gcc 13.3.0)
• 結果: WA
• 実行時間: -
• コード長: 4,621 bytes
• コンパイル時間: 1,022 ms
• コンパイル使用メモリ: 36,276 KB
• 実行使用メモリ: 15,616 KB
• 最終ジャッジ日時: 2024-09-13 22:27:28
• 合計ジャッジ時間: 4,739 ms
• ジャッジサーバーID （参考情報）: judge3 / judge5

ファイルパターン	結果
sample	-- * 3
other	AC * 2 WA * 1 TLE * 1 -- * 19

ソースコード

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<assert.h>

typedef struct AVLTreeNode{
  int size;
  int rank;
  int bias;
  struct AVLTreeNode *left;
  struct AVLTreeNode *right;
  unsigned char val[];
} AVLNode;

typedef struct AVLTreeHead{
  AVLNode *root;
  size_t valSize;
  int (*cmp)(const void *,const void *);
} AVLTree;

int getRank(const AVLNode *t){
  return t==NULL?0:t->rank;
}

int getSize(const AVLNode *t){
  return t==NULL?0:t->size;
}

int getBias(const AVLNode *t){
  return t==NULL?0:t->bias;
}

AVLNode* newAVLNode(const void *v,const size_t size){
  AVLNode *res=(AVLNode *)malloc(sizeof(AVLNode)+size);
  memcpy(res->val,v,size);
  res->size=1;
  res->rank=1;
  res->bias=0;
  res->left=NULL;
  res->right=NULL;
  return res;
}

void freeAllAVLNode(AVLNode *t){
  if(t==NULL) return;
  freeAllAVLNode(t->left);
  freeAllAVLNode(t->right);
  free(t);
}

void freeAVLNode(AVLNode *t){
  free(t);
  return;
}

AVLTree* newAVLTree(const size_t size,int (*cmp)(const void *,const void *)){
  AVLTree *res=(AVLTree *)malloc(sizeof(AVLTree));
  res->root=NULL;
  res->valSize=size;
  res->cmp=cmp;
  return res;
}

void update(AVLNode *t){
  if(t==NULL) return;
  int lrank=getRank(t->left);
  int rrank=getRank(t->right);
  t->rank=1+(lrank>rrank?lrank:rrank);
  t->size=1+getSize(t->left)+getSize(t->right);
  t->bias=lrank-rrank;
  return;
}

AVLNode* leftRotate(AVLNode *v){
  AVLNode *u=v->right;
  v->right=u->left;
  u->left=v;
  update(v);
  update(u);
  return u;
}

AVLNode* rightRotate(AVLNode *u){
  AVLNode *v=u->left;
  u->left=v->right;
  v->right=u;
  update(u);
  update(v);
  return v;
}

AVLNode* balance(AVLNode *t){
  if(t==NULL) return NULL;
  int b=getBias(t);
  if(b<=-2){
    if(getBias(t->right)>0) t->right=rightRotate(t->right);
    t=leftRotate(t);
  } else if(b>=2){
    if(getBias(t->left)<0) t->left=leftRotate(t->left);
    t=rightRotate(t);
  }
  return t;
}

AVLNode* insert_func(AVLNode *r,const void *v,AVLTree *t){
  if(r==NULL) return newAVLNode(v,t->valSize);
  if(t->cmp(r->val,v)>=0){
    r->left=insert_func(r->left,v,t);
  } else {
    r->right=insert_func(r->right,v,t);
  }
  update(r);
  return balance(r);
}

void insert(AVLTree *t,const void *v){
  t->root=insert_func(t->root,v,t);
  return;
}

int search(AVLTree *t,void *res){
  AVLNode *r=t->root;
  while(r!=NULL){
    int c=t->cmp(r->val,res);
    if(c==0){
      memcpy(res,r->val,t->valSize);
      return 1;
    } else if(c>0){
      r=r->left;
    } else {
      r=r->right;
    }
  }
  return 0;
}

typedef long long int int64;

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))

const int mod=1000000000+7;

int *fact=NULL;
int *iFact=NULL;
void init(const int n){
  fact=(int *)calloc(n+1,sizeof(int));
  fact[0]=1;
  int i;
  for(i=1;i<=n;i++) fact[i]=(int64)fact[i-1]*i%mod;
  int t=1;
  int a=fact[n];
  while(a>1){
    t=(int64)t*(mod-mod/a)%mod;
    a=mod%a;
  }
  iFact=(int *)calloc(n+1,sizeof(int));
  iFact[n]=t;
  for(i=n-1;i>=0;i--) iFact[i]=(int64)iFact[i+1]*(i+1)%mod;
}

int comb(int n,int k){
  if(!(0<=k && k<=n)) return 0;
  return (int64)fact[n]*iFact[k]%mod*iFact[n-k]%mod;
}

typedef struct {
  int n;
  int now;
  int leaf;
  int val;
} node;

int cmp(const void *a,const void *b){
  const node *p=(const node *)a;
  const node *q=(const node *)b;
  if(p->n   !=q->n) return p->n-q->n;
  if(p->now !=q->now) return p->now-q->now;
  if(p->leaf!=q->leaf) return p->leaf-q->leaf;
  return 0;
}

int calc(const int n,const int now,const int leaf){
  if(!(now<=n && now<=leaf)) return 0;
  if(now<leaf && now-1+(n-now)<leaf) return 0;
  if(leaf==1) return now==1?1:0;
  if(leaf==now){
    return comb(n-now+now-1,n-now);
  }
  if(n==now){
    return leaf==now?1:0;
  }
  static AVLTree *map=NULL;
  if(map==NULL) map=newAVLTree(sizeof(node),cmp);
  node t=(node){n,now,leaf,0};
  if(search(map,&t)){
    return t.val;
  }
  int res=0;
  int i,j;
  for(i=1;i<=leaf && i<=n-now;i++){
    for(j=MIN(i,now);j>=1 && i<=leaf-(now-j);j--){
      int next=comb(j-1+i-j,j-1);
      int hasChild=comb(now,j);
      res=(res+(int64)calc(n-now,i,leaf-(now-j))*hasChild%mod*next)%mod;
    }
  }
  t.val=res;
  insert(map,&t);
  return res;
}

void run(void){
  int n;
  scanf("%d",&n);
  int *cnt=(int *)calloc(n+1,sizeof(int));
  int i;
  for(i=0;i<n-1;i++){
    int a,b;
    scanf("%d%d",&a,&b);
    cnt[a]++;
    cnt[b]++;
  }
  int leaf=0;
  for(i=2;i<=n;i++){
    if(cnt[i]==1) leaf++;
  }
  init(200000);
  int ans=calc(n,1,leaf);
  printf("%d\n",ans);
}

int main(void){
  run();
  return 0;
}