TopCoder SRM 726 Div1 Medium HeroVacation

500-550pt位でもいいのかもしれない。
https://community.topcoder.com/stat?c=problem_statement&pm=14749

問題

1～Nのラベル付き木を成すを無向グラフが与えられる。
1～NのPermutation Qを考える。
Q[0]から初めて、順次Q[i]→Q[i+1]を最短経路で移動していくことを考えよう。
その過程における、各頂点の訪問回数を降順でソートしたとき、その数列が辞書順最大となるようなQを求めよ。

解法

辞書順最大の条件より、１か所を極端に多く訪問するようにしたい。
ということで、木の重心を求め、そこを何度も通るようにしよう。

重心を求めた後、各辺につながる頂点番号を列挙しよう。
Q[0]は重心とし、以後は最大の要素数を持つ辺の先の頂点を選択してQに追加する、を繰り返せばよい。

class HeroVacation {
	public:
	int N;
	vector<int> E[51];
	vector<int> D[51][51];
	vector<vector<int>> DS[51];
	
	void dfs(int cur,int pre) {
		if(D[cur][pre].size()) return;
		D[cur][pre].push_back(cur);
		FORR(e,E[cur]) if(e!=pre) {
			dfs(e,cur);
			FORR(v,D[e][cur]) D[cur][pre].push_back(v);
		}
	}
	
	vector <int> getPermutation(vector <int> p) {
		int i,j,x,y;
		N=p.size()+1;
		FOR(i,N) E[i].clear();
		FOR(x,N) FOR(y,N) D[x][y].clear();
		FOR(i,N-1) {
			E[p[i]].push_back(i+1);
			E[i+1].push_back(p[i]);
		}
		FOR(i,N-1) dfs(p[i],i+1),dfs(i+1,p[i]);
		
		int mi=1010,id=-1;
		FOR(i,N) {
			int ma=0;
			DS[i].clear();
			FORR(e,E[i]) {
				ma=max(ma,(int)D[e][i].size());
				DS[i].push_back(D[e][i]);
			}
			if(ma<=mi) mi=ma, id=i;
		}
		
		vector<int> R;
		R.push_back(id);
		vector<vector<int>> Ds=DS[id];
		int pre=-1;
		FOR(i,N-1) {
			int ma=0,id=-1;
			FOR(j,Ds.size()) {
				if(Ds[j].size()>ma && pre!=j) ma=Ds[j].size(), id=j;
			}
			pre=id;
			R.push_back(Ds[id].back());
			Ds[id].pop_back();
		}
		
		return R;
		
	}
}

まとめ

問題が悪くないだけに、CFと重ねたのはもったいないな。