PKU 3385 Genealogy

http://poj.org/problem?id=3385
ある宇宙人が家系図を持っている。
この宇宙人にはp人以下の親しかいないはずなのに、その家系図にはpよりも多い部分がある。
矛盾しないように間に親を挟む時、最小で何人挟めばよいかを答えろというような問題。

何人の親をはさむと、直接の先祖を何人持つことが出来るかを考えました。
変なことやって1WA。
あと入力が多いのか1TLE。

int pa[100001];
int memo[100001];
int n,d;

main(){
  scanf("%d%d",&n,&d);

  for(int i=d+1;i<=n;++i){
    if((i-1-d)%(d-1)==0)memo[i]=memo[i-1]+1;
    else memo[i]=memo[i-1];
  }

  rep(i,n){
    int t;
    scanf("%d",&t);
    ++pa[t];
  }

  int ans=0;
  rep(i,n+1)ans+=memo[pa[i]];
  cout<<ans<<endl;
}