https://www.facebook.com/hackercup/problem/232395994158286/
N頂点の二分木がある。
各頂点に以下のルールで数を割り当てていく。
全て満たすような割り当てがあれば、それを答えよ。
- pre-order順で回ったとき、post-order順で回ったときで、それぞれ各頂点の数を配列にすると、等しい配列ができる
- 各頂点の数は1~Kのどれか
- 1~Kの数がどれも最低1つは割り当てられる
前提知識
考察過程
1. pre-order, post-orderで回ると、対応する頂点の組が得られる
2. 対応する頂点は同じ数になる必要があるので、同じグループと考えることができる
3. これはUnionFindか
4. 違うグループに属するなら、独立に数の割り当てを考えられる
5. グループの個数が数の割り当ての最大個数となる
6. あとは適当に構築
解法
3段階で解いていく
1. pre-order、post-orderで頂点を巡って、頂点の数を取ってくる順番をそれぞれ得る
2. 1番目通し、2番目通し、…は同じ数になるのでUnionFindでグループ化する
3. それぞれのグループに数を適切に割り当てる
1. pre-order、post-orderで頂点を巡って、頂点の数を取ってくる順番をそれぞれ得る
これはdfsで順番を作っていこう。
配列に追加する場所だけ違うので、フラグを使って1つにまとめている(dfs関数)
2. 1番目通し、2番目通し、…は同じ数になるのでUnionFindでグループ化する
題名通りUnionFindでグループ化していこう。
3. それぞれのグループに数を適切に割り当てる
各グループに1から順番に割り当てていき、Kを割り当てた後は、全てKを割り当てるようにする。
もし、順番に割り当てていき、Kまで行かなかったら、グループ数がK個未満ということなので、
この場合は有効な割り当てが無いとして「-1」を出力する。
int N, K, A[2010], B[2010]; //--------------------------------------------------------------------------------------------------- void dfs(int cu, int isPost, vector<int> &v) { if (cu < 0) return; if (isPost == 0) v.push_back(cu); dfs(A[cu], isPost, v); dfs(B[cu], isPost, v); if (isPost == 1) v.push_back(cu); } //--------------------------------------------------------------------------------------------------- int L[2010]; void solve() { cin >> N >> K; rep(i, 0, N) { cin >> A[i] >> B[i]; A[i]--; B[i]--; } vector<int> pre, post; dfs(0, 0, pre); dfs(0, 1, post); UnionFind uf(N); rep(i, 0, N) uf(pre[i], post[i]); int num = 0; rep(i, 0, N) if (uf[i] == i) { if (num < K) num++; L[i] = num; } if (num != K) { printf("Impossible\n"); return; } rep(i, 0, N) { if (i) printf(" "); printf("%d", L[uf[i]]); } printf("\n"); } //--------------------------------------------------------------------------------------------------- void _main() { int T; cin >> T; rep(t, 0, T) { printf("Case #%d: ", t + 1); solve(); fprintf(stderr, "Finish : %d\n", t+1); } }