TopCoder SRM 598 Div1 Hard TPS

問題

n個の都市が双方向に通行可能な道でつながれていて、木をなしている。
ここにどの都市にいるかを検知するシステムを作る。

発信機を好きな都市に置くことができて、
受信機ではそれぞれの発信機からの距離（木における距離）を知ることが出来る。
全ての都市で、自分の位置を一意に特定するために必要な発信機を置く個数の最小値を求めよ。

制約条件

n≦50

方針

グラフがn=1だったら発信機は不要。
n = 2だったらひとつ置けばいい。

適当に次数が２以上の頂点を根として考える。
グラフに分岐があったとすると、分岐した先の頂点では、その前に置いた発信機は全て役に立たなくなる。
なので必ず分岐の先に一つ以上の発信機を置く必要がある。

根から直接の子が、枝分かれのない子が全てだったとすると、
一つを残してほかの枝の葉に発信機を置くのが最善。

枝分かれがある子があったらそれらのそれぞれには上の考察から、全部一つ以上発信機をおく必要があって、
省略できるのは枝分かれのない子（があれば）一つ分だけ。

で、枝分かれのある子については再帰して同じことをやればいい。

こんな自明な貪欲でHardが通るわけないだろうと思ったんだけど、
ダメそうなところが見つからないので書いてみたら通ってしまってびっくりした。何なんだこれは。

ソースコード

int n;
bool e[50][50];

bool line(int c, int p){
	int next = -1;
	rep(i, e[c].size()) if(e[c][i] != p){
		if(next < 0) next = e[c][i];
		else return 0;
	}
	if(next < 0) return 1;
	return line(next, c);
}
int rec(int c, int p){
	int idx = -1, res = 0;
	
	rep(i, e[c].size()) if(e[c][i] != p){
		if(line(e[c][i], c)){
			idx = i;
			res++;
		}
		else res += rec(e[c][i], c);
	}
	return res - (idx >= 0);
}

class TPS {
	public:
	int minimalBeacons(vector <string> linked) {
		n = e.size();
		rep(i, n) rep(j, n) e[i][j] = linked[i][j] == 'Y';
		
		if(n == 1) return 0;
		if(n == 2) return 1;
		
		int root = -1;
		rep(i, n) if(e[i].size() > 1) root = i;
		return rec(root, -1);
	}
};