PKU 2732 Countdown

http://poj.org/problem?id=2732

家系図が与えられる。
d回子供をたどって到達する人数の多いほうから3人ほど答えろというような問題。

やるだけ。

map<string,int> stoi;
vector<string> itos;

int get(string& a){
  if(stoi.count(a)) return stoi[a];
  stoi[a] = SZ(itos);
  itos.pb(a);
  return SZ(itos)-1;
}

vector<int> G[1000];


int dfs(int p,int d){
  if(d==0) return 1;
  int ret=0;
  FOR(it,G[p]) ret += dfs(*it,d-1);
  return ret;
}

void solve(int ca){
  if(ca) cout<<endl;
  printf("Tree %d:\n",ca+1);

  stoi.clear();
  itos.clear();

  int n,d;
  cin>>n>>d;
  rep(i,1000) G[i].clear();

  rep(i,n){
    string p;
    cin>>p;
    int pi=get(p);
    int m;
    cin>>m;
    rep(j,m){
      cin>>p;
      int c=get(p);
      G[pi].pb(c);
    }
  }
  vector<pair<int,string> > ans;
  rep(i,1000){
    int g=dfs(i,d);
    if(g) ans.pb(mp(-g,itos[i]));
  }
  sort(ALL(ans));
  rep(i,SZ(ans)){
    if(i>=3 && ans[i].F!=ans[i-1].F) break;
    cout<<ans[i].S<<' '<<-ans[i].F<<endl;
  }
}

main(){
  int t;
  cin>>t;
  rep(i,t) solve(i);
}