Cell Phone Network (PKU 3659)

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

問題

n頂点の木が与えられる。全ての頂点との距離が1以下となる頂点集合の最小サイズを求めよ。
1<=n<=10,000

解法

dfsで各頂点の深さを求めて、深い方から順にその点がまだカバーされてなかったら親の頂点を頂点集合にいれていく。