POJ 3385 Genealogy

問題

宇宙人は、1人の子に対して親が最大d人までいる。
親子関係がツリーとして与えられるが、一部が欠けていて、親がd人より多くなっている宇宙人がいる。

ツリーに適当に宇宙人を挿入し、1人の子の親がd人以下にしたい。
挿入しなければならない宇宙人の最小の数を求めよ。

制約条件

n≦100000

方針

宇宙人を頂点とするグラフを考える。
宇宙人Aが宇宙人Bの子であるとき、A→Bのように辺を貼る。

このグラフのある頂点において、子ノードがd個以上のm人だったとき、
m→m/d+m%dと言う風に、d人の親をもつ子を置けるだけgreedyに置いてノードを減らすのが最善の置き方。
これは、毎回愚直に計算すると時間がかかるので、あらかじめDPにより求めておく。

あとはこれをグラフの全て頂点に対してやればいい。
が、TLEがやたら厳しい。
O(n)の解法でもTLEする。

グラフでvectorを使わないようにしたら本当にギリギリで(1000ms)通った。
入力をscanf使わず自力でreadするのが吉なのだろうか、

ソースコード

const int MAX=100001;
int n,d;
int dp[MAX];
int G[MAX],es,to[MAX],next[MAX],deg[MAX];

int dfs(int c){
  int m=deg[c], res=dp[m];
  for(int e=G[c];e;e=next[e])res+=dfs(to[e]);
  return res;
}
int main(){
  scanf("%d%d",&n,&d);
  es=1;
  rep(i,n){
    int a; scanf("%d",&a);
    deg[a]++;
    next[es]=G[a];
    to[es]=i+1;
    G[a]=es++;
  }
  for(int i=d+1;i<=n;i++)
    dp[i]=i/d+dp[i/d+i%d];
  
  printf("%d\n",dfs(0));
  return 0;
}