Codeforces #596 Div1 D. Tree Factory

変わった問題。
http://codeforces.com/contest/1246/problem/D

問題

0～(N-1)のラベルを持つN頂点の根付き木が与えられる。
このグラフの根頂点は0番であり、親の方が子より番号が小さい。

この木を、枝分かれのないグラフから作りたい。
まず、分岐がない深さ(N-1)のグラフを考える。
その際、各頂点のラベルは0～(N-1)まで1回ずつ振れば、位置は問わない。

ここで、頂点vの親頂点をp(v)としてあらわすとする。
頂点vを1つ選び、v-p(v)間の辺をv-p(p(v))間に張り替える、ということを行う。
こうして入力の木を作りたい。
張り替え回数が最小となるような、初期のグラフと張り替え順を求めよ。

解法

枝分かれのないグラフにおいて、最終的に深い位置に来る葉の下に浅い位置に来る葉が来ると、張り替え順が増える。
そのためゴールとなるグラフにおいて、浅い葉が根に近い位置に来るよう、DFS順で番号をふっていこう。

int N;
int P[101010];
vector<int> E[101010];
int D[101010];
int MD[101010],MV[101010];


vector<int> Vs;
vector<int> step;

void dfs(int cur) {
	vector<vector<int>> C;
	Vs.push_back(cur);
	FORR(e,E[cur]) {
		C.push_back({MD[e],MV[e],e});
	}
	sort(ALL(C));
	int i,j;
	FOR(i,C.size()) {
		dfs(C[i][2]);
		if(i<C.size()-1) {
			FOR(j,C[i][0]-D[cur]) step.push_back(C[i+1][2]);
		}
	}
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x;
		P[i+1]=x;
		E[x].push_back(i+1);
		D[i+1]=D[x]+1;
		MD[i+1]=D[i+1];
		MV[i+1]=D[i+1];
	}
	
	for(i=N-1;i>=0;i--) {
		FORR(e,E[i]) {
			if(MD[e]>MD[i]) MD[i]=MD[e],MV[i]=MV[e];
		}
	}
	
	dfs(0);
	
	FORR(v,Vs) cout<<v<<" ";
	cout<<endl;
	cout<<step.size()<<endl;
	FORR(s,step) cout<<s<<" ";
	cout<<endl;
	
}

まとめ

Dの割に簡単と思ったけど、これ2250ptなのね…。