Codeforces Round #318 [RussianCodeCup Thanks-Round] (Div. 1) C. Bear and Drawing

納得できたようなできてないような。

問題

codeforces.com

解法

こどふぉ解説の図を使わせていただきます。

codeforces.com

木が 2 行の紙に書ける場合は, 木は下図のように, 「メインになる道(青)が一本あって, それに付属する頂点は一行に収まる(赤丸で囲ってあるところ)」という感じになっているはずです。

ちょっと注意なのは, 一番左の頂点と一番右の頂点は決まっているということです。今回の図では, 例えば一番左の頂点から辺を伸ばしていけば一行じゃなくて 2 行分使えるじゃん, と思うかもしれませんが左端の頂点は決まっているのでそういうのはナシです。

で, じゃあメイン道が決まったとして, 一行に収まるような頂点群はどんなものがあるかを考えると, これは「Y 字型」(左下)と「直線型」(右上)の 2 種類です。

ということで, やりたいことは,
それにくっついている頂点を考え, それが Y 字型のものか, 直線型のものか, それ以外のものかを見分ける。「それ以外のもの」がありすぎると 2 行の紙に収めることは出来ず, そうでなければ収められる
というような感じです。具体的に詰めていきます。

直線型かや Y 字型かを判定するために, del という変数を使います。これは, 以下のような感じです。

[f:id:mayokoex:20150903085737p:plain]

次数が 1 のところからスタートして次数が 2 以内の頂点はすべて消していく(del を true にする)感じです。「端っことつながってるからそこはなくても同じ」というイメージですかね。

次に, 消されていない頂点に対して, leg という値を定義します。これは, 「端っことつながっている頂点」というような意味合いで, これは頂点が「消された頂点」とつながっている数で計算できます。

これらの値を求めると, 各頂点について, その頂点に隣り合っている消されていない頂点 ch が
(次数) - min(2, leg[ch]) <= 1 なら, ch は Y 字型または直線型の形を形成する起点となる頂点なので, 1 次元で表わせセーフです。一方 (次数) - min(2, leg[ch]) > 1 だと 1 次元では表せず, このような頂点が 3 つ以上隣り合っていると死にます。

const int MAXN = 100010;
vector<int> G[MAXN];
bool del[MAXN];
int leg[MAXN];

void dfs(int v, int p = 0) {
    del[v] = true;
    for (int ch : G[v]) {
        if (ch == p) continue;
        if (G[ch].size() <= 2) dfs(ch, v);
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    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);
    }
    for (int i = 1; i <= N; i++) if (G[i].size() == 1) dfs(i);
    for (int i = 1; i <= N; i++) {
        for (int ch : G[i]) if (del[ch]) leg[i]++;
    }
    for (int i = 1; i <= N; i++) {
        if (del[i]) continue;
        int cnt = 0;
        for (int ch : G[i]) if (!del[ch]) {
            if (G[ch].size() - min(2, leg[ch]) > 1) cnt++;
        }
        if (cnt > 2) {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}