Mail.Ru Cup 2018 Round 3 : D. Decorate Apple Tree

なんだこれ…。
http://codeforces.com/contest/1056/problem/D

問題

N頂点で根付き木が与えられる。
葉頂点に、なんらかの色の電気をつける。

頂点中K個に対し、そのSubTree内の葉が異なる色の電気がつくようにしたい。
その場合、最小で葉を何色で塗り分ければよいか、K=1～Nに対し答えよ。

解法

各頂点に対し、DFSでSubTree内の葉頂点数を数える。
あとはソートして昇順に出力するだけ。

int N;
vector<int> E[101010];
int num[101010];

int dfs(int cur) {
	int v=(E[cur].empty());
	FORR(e,E[cur]) v+=dfs(e);
	num[cur]=v;
	return v;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N-1) {
		cin>>x;
		E[x-1].push_back(i+1);
	}
	
	dfs(0);
	sort(num,num+N);
	
	FOR(i,N) cout<<num[i]<<" ";
	
}

まとめ

こっち先に解くべきだった…。