Codeforces Round #190 Ciel the Commander

問題

節点数Nの木が与えられる。それぞれの節点にはランクが与えられる。ランクはA-Zまでのアルファベットで、若い文字の方がランクが高いとする。ランクが同じ任意の二節点のパス上には、必ずより高いランクを持った節点が少なくとも一つあるようにしたい。各節点にランクを割り振れ。

解法

木の高さがなるべく低くなるように節点vを選ぶ。vにはランクAを与える。節点vを木集合から除くと二つの部分木が得られる。えられた部分木について同様のことを再帰的に繰り返す。これ系のパターンはCodeforcesにはよく出る。DFSを二回すればよくて、一つ目のDFSでは部分木の節点数をカウントし、二つ目のDFSでは最適な根を選ぶ。一つ目のDFSで得られた値をうまく伝搬することで、二つ目のDFSの計算を高速に行うことができる。

ソースコード

using namespace std;

#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  
#define MP(x,y) make_pair(x,y)

int N;
vector<int> edge[100000];
int rank[100000];
int size[100000];
bool cut[100000];

// get the number of nodes in the subset a node v belong to.
void getSize(int v, int par = -1) {
    size[v] = 1;
    REP (i, edge[v].size()) {
        int w = edge[v][i];
        if (w == par || cut[w]) continue;
        getSize(w, v);
        size[v] += size[w];
    }
}

// select an optimal root node from the subset a node v belong to.
pair<int, int> chooseRoot(int v, int par, int total) {
    pair<int, int> ret = MP(1<<30, -1);

    int rm = total;
    int sub = 0;
    REP (i, edge[v].size()) {
        int w = edge[v][i];
        if (w == par || cut[w]) continue;
        ret = min(ret, chooseRoot(w, v, total));
        sub = max(sub, size[w]);
        rm -= size[w];
    }
    sub = max(sub, rm);
    ret = min(ret, MP(sub, v));
    return ret;
}

void dfs(int v, int depth) {
    getSize(v);
    int r = chooseRoot(v, -1, size[v]).second;
    rank[r] = depth;
    cut[r] = true;
    REP (i, edge[r].size()) {
        int w = edge[r][i];
        if (cut[w]) continue;
        dfs(w, depth+1);
    }
}

int main() {
    cin >> N;
    REP (i, N-1) {
        int a, b;
        cin >> a >> b;
        edge[--a].push_back(--b);
        edge[b].push_back(a);
    }

    dfs(0, 0);

    REP (i, N) {
        char c = 'A' + rank[i];
        putchar(c);
        putchar(' ');
    }
    puts("");

    return 0;
}