WARush

SRMの結果とか、解けた問題のコードを書いていきます

Codeforces #190 Div2 E "Ciel the Commander"

問題

http://codeforces.com/contest/322/problem/E

シエルはツリーランドの指揮官に就任した。ツリーランドはその名の示すとおり、n個の都市をn-1の双方向の道で繋いであり、2つの任意の都市を結ぶ経路が必ずある、(いわば木構造になっている)。

シエルは各都市に士官を配置したい。それぞれの士官はA - Zの文字で表されるランクを持っている。よって26階級あることになり、Aが一番良く、Zが一番下である。

各ランクの士官は十分な人数がいる。しかし、次のような特別なルールがある。もし、xとyという2つの都市に、同じランクの士官が配置されていた場合、xとyを結ぶ経路上に、より高いランクが配置された都市zがなくてはならない。このルールは同じランクの士官の通信を監視できるようにするため設けられている。

都市の情報が与えられるので、士官を配置せよ。出来なければそれを示唆する事。

制約

2 <= n <= 10^5


チュートリアルを見て

木というものは、ある頂点を選んで削除すると、複数の部分木に分割する。もともとの木の頂点数の半分以下となるような部分木にできるような頂点を選び、そこにランクの高い順に士官を配置していく。
f:id:Ekaing:20130717225009j:plain
f:id:Ekaing:20130717225016j:plain
f:id:Ekaing:20130717225022j:plain
f:id:Ekaing:20130717225028j:plain

こうすればあら不思議。必ず同じランクの都市の経路上にそれよりランクの高い都市があることになる。さらに、半分以下に分割しているので、26個のランクがあれば10万なんて余裕で網羅できる。


ソースコード

int N;
vector<int> G[100050];
bool chk[100050];
int num[100050];
int ans[100050];

// 部分木を根付き木にして下にある頂点数を出す
int check_num( int p, int v ){
    chk[v] = true;
    int res = 1;
    for( int i = 0; i < G[v].size(); i++ ){
        int c = G[v][i];
        if( c == p || ans[c] != -1 ) continue;
        res += check_num( v, c );
    }
    return num[v] = res;
}

// 半分以下に出来る頂点を探る
int get_half_vartex( int p, int v, int t ){
    int res = v;
    for( int i = 0; i < G[v].size(); i++ ){
        int c = G[v][i];
        if( c == p || ans[c] != -1 ) continue;
        if( num[c] > t ){
            res = get_half_vartex( v, c, t );
        }
    }
    return res;
}

void rec(){
    for( int rank = 0; rank < 26; rank++ ){
        memset( chk, false, sizeof(chk) );
        for( int i = 1; i <= N; i++ ){
            if( chk[i] || ans[i] != -1 ) continue;
            // dfsで各頂点の保持数を調べる
            int n = check_num( -1, i );
            // この頂点から数えて半分以下に出来る頂点を探る
            int v = get_half_vartex( -1, i, n / 2 );
            // その頂点のランクをrankにする
            ans[v] = rank;
        }
    }
}


int main() {
    // 入力 グラフ作成
    cin >> N;
    for( int i = 0; i < N - 1; i++ ){
        int a, b;
        cin >> a >> b;
        G[a].push_back( b );
        G[b].push_back( a );
    }

    // 答えを出す
    memset( ans, -1, sizeof(ans) );
    rec();

    // 出力
    for( int i = 1; i <= N; i++ ){
        printf( "%c ", ans[i] + 'A' );
    }
}