なんだこの問題…。
http://community.topcoder.com/stat?c=problem_statement&pm=13746
問題
N頂点の根付き木を考える。
ここからいくつかのパスを取りたい。
その際、あるパス上の頂点の祖先が、他のパス上の頂点となる、ということが無いようにしたい。
選べる最大パス数はいくつか。
解法
問題をよく読むと、パスの長さは0であっても良いことがわかる。
よって葉の頂点数を答えればよい。
class UnrelatedPaths { public: int maxUnrelatedPaths(vector <int> parent) { int i,N=parent.size()+1; int hc[52]={}; for(i=N-1;i>=1;i--) hc[parent[i-1]] = 1; int ret=0; FOR(i,N) ret += 1-hc[i]; return ret; } }
まとめ
せめてパス長が1以上とかの縛りを付ければよかったのにな。
…自分は最初暗黙にその縛りを仮定して解こうとしてしまった。