なんだこれ…。
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]<<" "; }
まとめ
こっち先に解くべきだった…。