けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

Codeforces 190 DIV1 C - Ciel the Commander (重心分解)

てんぷら君が解いていたのを見て...

問題へのリンク

問題概要

 N 頂点のツリーが与えられる。
ツリーの各頂点に 'A' 〜 'Z' のラベルを割り当てたい。アルファベット順に rank が低くなっていくものとする ('A' が最高ランク)。

  • 任意の 2 頂点 u, v について、u と v とのラベルが同一ならば、パス u-v 間にある内点の中に、 u, v のラベルよりもランクが高いものが存在する

という条件を満たすようにすることは可能か?可能なら 1 つ求めよ。

制約

  •  2 \le N \le 10^{5}

考えたこと

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 以内の根付き木が作れるかどうかであるが、そこで重心分解の出番である。毎回すべての部分木のサイズが元の半分以下になるようにできるので、 O(\log{n}) の深さの根付き木が作れる。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;
}