てんぷら君が解いていたのを見て...
問題概要
頂点のツリーが与えられる。
ツリーの各頂点に 'A' 〜 'Z' のラベルを割り当てたい。アルファベット順に rank が低くなっていくものとする ('A' が最高ランク)。
- 任意の 2 頂点 u, v について、u と v とのラベルが同一ならば、パス u-v 間にある内点の中に、 u, v のラベルよりもランクが高いものが存在する
という条件を満たすようにすることは可能か？可能なら 1 つ求めよ。
制約
考えたこと
「2018 第4回ドワンゴからの挑戦状 予選 E - ニワンゴくんの家探し」によく似ている気がする。
ツリーを根付き木にしたならば、根から順に深さに応じて 'A', 'B', ..., と割り当てていけば実現できそうである。なぜならば、寝つき木のパス u-v は、u と v の最近共通祖先を w とすると
- w が u でも v でもない (w から見て u も v もより深いところにいる)
- w = u or w = v
のいずれかになるが、後者の場合 u と v とのラベルが等しくなることはありえない。したがって前者のみだが、w が条件を満たす内点になる。
さて問題は、深さ 26 以内の根付き木が作れるかどうかであるが、そこで重心分解の出番である。毎回すべての部分木のサイズが元の半分以下になるようにできるので、 の深さの根付き木が作れる。26 あれば十分である。
#include <iostream> #include <vector> using namespace std; /* vector<int> tree[MAX_V]; // ツリーを隣接リスト形式のグラフ構造で表したもの int sizeSubtree[MAX_V]; // sizeSubtree[v] := v を根とする部分ツリーのサイズ (分割統治の毎ステップごとに再利用) bool isRemoved[MAX_V]; // isRemoved[v] := v が既に取り除かれたかどうか int whoIsParent[MAX_V]; // whoIsParent[v] := ツリーDP時に v の親が誰だったか */ typedef vector<vector<int> > TREE; int iter; vector<int> res; struct TreeCenteroid { TREE tree; // results vector<int> centroids; // intermediate results vector<int> sizeSubtree, isRemoved, whoIsParent; // init void init(const TREE &tree_) { tree = tree_; centroids.clear(); sizeSubtree.resize((int)tree.size()); whoIsParent.resize((int)tree.size()); isRemoved.resize((int)tree.size()); for (int i = 0; i < (int)tree.size(); ++i) isRemoved[i] = false; } // subroutine void SubFindCentroid(int v, int size, int p = -1) { sizeSubtree[v] = 1; whoIsParent[v] = p; bool isCentroid = true; for (auto ch : tree[v]) { if (ch == p) continue; if (isRemoved[ch]) continue; SubFindCentroid(ch, size, v); if (sizeSubtree[ch] > size / 2) isCentroid = false; sizeSubtree[v] += sizeSubtree[ch]; } if (size - sizeSubtree[v] > size / 2) isCentroid = false; if (isCentroid) centroids.push_back(v); } // first: centroid, second: vectors of (adj-node, size of adj-tree) void FindCentroid(int root, int size, int iter = 0) { centroids.clear(); SubFindCentroid(root, size); int center = centroids[0]; res[center] = iter; isRemoved[center] = true; for (auto ch : tree[center]) { if (isRemoved[ch]) continue; if (ch == whoIsParent[center]) { FindCentroid(ch, size - sizeSubtree[center], iter + 1); } else { FindCentroid(ch, sizeSubtree[ch], iter + 1); } } } }; int main() { int N; cin >> N; TREE tree(N); for (int i = 0; i < N-1; ++i) { int u, v; scanf("%d %d", &u, &v); --u, --v; tree[u].push_back(v); tree[v].push_back(u); } res.resize(N); TreeCenteroid tc; tc.init(tree); tc.FindCentroid(0, N); for (int v = 0; v < N; ++v) { cout << (char)('A' + res[v]); if (v != N-1) cout << " "; } cout << endl; }
