Codeforces #612 Div1 B. Numbers on Tree

本番割とすんなり解いてる。
https://codeforces.com/contest/1286/problem/B

問題

根付き木が与えられる。
各頂点vにはパラメータC[v]が与えられる。

ここで、各頂点に整数A[v]を設定することを考える。
頂点vのSubTree内に、A[u]＜A[v]となる頂点uがC[v]個となるようにAを構築せよ。

解法

まず、C[v]はvのSubTreeの頂点数未満でなければならない。
そこでSubTree内の頂点を数え上げ、この条件を判定してしまおう。

次に、各頂点に値を振ることを考える。
1～Nのうち、未使用の整数集合をもってDFSしていく。
頂点v以下を処理するとき、集合中で小さい順にvのSubTree内の頂点数分の要素を使い切ることを考えよう。
その時、A[v]には集合中の小さい方から(0-indexedで)C[v]番目を使うようにする。
それ以前の要素は、DFSの探索中にSubtree内のどこかで使い切るので、条件を必ず満たす。

int N;
int P[2020];
vector<int> E[2020];
int C[2020];
int child[2020];
vector<int> cand;
int num[2020];
vector<int> valid;

int dfs(int cur){
	child[cur]=1;
	FORR(e,E[cur]) child[cur]+=dfs(e);
	if(child[cur]-1<C[cur]) {
		cout<<"NO"<<endl;
		exit(0);
	}
	return child[cur];
}

void dfs2(int cur) {
	num[cur]=valid[C[cur]];
	valid.erase(valid.begin()+C[cur]);
	FORR(e,E[cur]) dfs2(e);
	
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	int root=0;
	FOR(i,N) {
		cin>>P[i+1]>>C[i+1];
		E[P[i+1]].push_back(i+1);
		if(P[i+1]==0) root=i+1;
	}
	dfs(root);
	FOR(i,N) valid.push_back(i+1);
	dfs2(root);
	cout<<"YES"<<endl;
	FOR(i,N) cout<<num[i+1]<<" ";
	cout<<endl;
}

まとめ

なんか問題名が他と被りそう。