PKU 3342 Party at Hali-Bula
http://poj.org/problem?id=3342
あるパーティー会場にn人の人を集めたい。
n人の人は組織に所属しており、ビッグボス以外の人は必ず一人の上司を持っている。
このとき、パーティー会場に部下とその直近の上司がいると居心地が悪いので、そのような組み合わせが起きないように出来るだけ多くの人数を招待したい。
そのような人数と、その組み合わせがユニークなものなのかを判定しろというような問題。
木のDP的な問題。
あるノードより下でユニークなのかを判定する再帰関数で条件分けとかを頑張る。
map<string,set<string> >app; pair<PI,PI> dfs(const string&name){ pair<PI,PI> ret(mp(0,0),PI(0,1)); set<string>::iterator end=app[name].end(); for(set<string>::iterator i=app[name].begin();i!=end;++i){ pair<PI,PI> ch=dfs(*i); ret.S.F+=max(ch.S.F,ch.S.S); ret.F.F|=ch.S.F==ch.S.S; if(ch.S.F>=ch.S.S)ret.F.F|=ch.F.F; if(ch.S.S>=ch.S.F)ret.F.F|=ch.F.S; ret.S.S+=ch.S.F; ret.F.S|=ch.F.F; } return ret; } main(){ int n; while(cin>>n,n){ string big; cin>>big; app.clear(); rep(i,n-1){ string a,b; cin>>a>>b; app[b].insert(a); } pair<PI,PI> ans=dfs(big); cout<<max(ans.S.F,ans.S.S)<<' '; if(ans.S.F==ans.S.S || ans.S.F>ans.S.S && ans.F.F || ans.S.S>ans.S.F && ans.F.S)cout<<"No"<<endl; else cout<<"Yes"<<endl; } }