TopCoder SRM 630 Div1 Easy Egalitarianism3

SRM630は不参加。
時間的には苦戦したけど、Easy/Medium1発正答だったので出ておけばよかったな…。
http://community.topcoder.com/stat?c=problem_statement&pm=13284

問題

N点からなる木を成したグラフが与えられる。
各辺は無向辺で長さを持つ。

N点の部分集合Sのうち、S中どの２要素の最短距離も等しくなるようなものの最大頂点数を答えよ。

解法

N=1の時は答えは1で確定なので、以後はN>=2を前提とする。
まず、Sを２頂点にすれば２要素の最短距離は常に等しいので、答えは最低でも2となる。

今回のグラフが木であることを活用すると、Sが３要素以上となるには、ある頂点xに対し、そこから等距離の点が３個以上あり、それらをSに入れればよい。

ただしxとの距離が等しい頂点群でも最短経路にxを通らない頂点対はSに含められないので、１つの部分木あたり同じ距離の点は１つだけ含めるようにすればよい。

int mat[51][51];
vector<int> E[51];

class Egalitarianism3 {
	public:
	int maxCities(int n, vector <int> a, vector <int> b, vector <int> len) {
		int i,j,k,x,y;
		FOR(x,n) FOR(y,n) mat[x][y]=10000000;
		FOR(i,n) mat[i][i]=0;
		FOR(i,n) E[i].clear();
		FOR(i,n-1) E[a[i]-1].push_back(b[i]-1);
		FOR(i,n-1) E[b[i]-1].push_back(a[i]-1);
		FOR(i,n-1) mat[a[i]-1][b[i]-1]=mat[b[i]-1][a[i]-1]=len[i];
		FOR(i,n) FOR(x,n) FOR(y,n) mat[x][y]=min(mat[x][y],mat[x][i]+mat[i][y]);
		
		int ma=min(2,n);
		FOR(x,n) {
			map<int,int> M;
			FOR(y,E[x].size()) {
				int c=E[x][y];
				set<int> S;
				FOR(i,n) if(mat[i][x]==mat[i][c]+mat[c][x]) S.insert(mat[i][x]);
				ITR(it,S) M[*it]++;
			}
			ITR(it,M) ma=max(ma,it->second);
		}
		
		return ma;
	}
}

まとめ

意外に正答率が低かったけどどのケースなんだろうな。Sが最小２要素でもいい点かな？