問題概要

n ノードの木が与えられる．木の中で，次数が偶数の頂点を destroy できる．頂点を destroy すると，その頂点につながっている辺は全て消える．全ての頂点を destroy することは可能か答えよ．もし可能なら，頂点を destroy する順番を答えよ．

解法概要

WA を自力で解決できず解説をチラ見．

nの偶奇だけで YES/NO が決まってしまうらしい． destroy できるのは次数が偶数の頂点だけなので，1 頂点を destroy することで減る辺も偶数本である．そのため，辺が奇数本だと全部の辺を消し切ることができない．偶数本だとできる．木の辺が奇数本あるということは木の頂点が偶数個あるということだから，n が奇数ならば YES，偶数ならば NO である．

ここで，destroy の順番くらいは自分で考えるぞと意気込むもこちらも結局は公式解説とkmjpさんのブログでの解説に頼ることに．

結局各頂点において

. SubTree内の頂点数が偶数個の子頂点を探索する

. 見ている頂点を消す

. SubTree内の頂点数が奇数個の子頂点を探索する

の順を取ればよい。

(出典: Codeforces #475 B. Destruction of a Tree - kmjp's blog)

とのこと．

なるほど．これを自分の中で消化してみる．

部分木の頂点数が偶数の子ノードは今見ているノード v を消さなくても消せる．頂点数が偶数の部分木は辺の数が奇数で，そのsubtree の頂点から v に生えている辺を入れると辺の数が偶数になるため．

v を根とする部分木を考えたときに，頂点数が偶数個の部分木の根となっている子ノードとその子孫を全部消したとき，残る頂点の数は奇数となる (全体の頂点数は奇数であるため) ．そのため， v に「頂点数が奇数個の部分木」が偶数個ぶら下がっている状態になる．つまり v は次数が偶数となっており，destroy 可能である． v を消去すると次数が奇数だった子ノードたちの次数が偶数となり， destroy できるようになる．

このようにすると，全てのノードを destroy できる．ノード数が奇数ならば全てのノードが destroy できることから，ノード数が奇数 / 偶数の部分木の destroy 方法を再帰的に考えられるか がミソっぽい．

ソースコード

#include <iostream>
#include <vector>

using namespace std;

const int MAX_N = 200000;

vector<int> graph[MAX_N];
vector<int> node_num(MAX_N, 0);
int n;

void destroy(int i) {
    cout << i+1 << endl;
}

int count_dfs(int node, int par) {
    node_num[node] = 1;
    for(int nxt: graph[node]) {
        if(nxt == par) continue;
        node_num[node] += count_dfs(nxt, node);
    }
    return node_num[node];
}

void destroy_dfs(int node, int par) {
    for(int nxt: graph[node]) {
        if(nxt == par) continue;
        if(node_num[nxt] % 2 == 0) destroy_dfs(nxt, node);
    }
    destroy(node);
    for(int nxt: graph[node]) {
        if(nxt == par) continue;
        if(node_num[nxt] % 2 == 1) destroy_dfs(nxt, node);
    }
}

int main() {
    cin >> n;
    int x;
    for(int i=0;i<n;++i) {
        cin >> x;
        if(x) {
            --x;
            graph[x].push_back(i);
            graph[i].push_back(x);
        }
    }

    if(n % 2 == 0) {
        cout << "NO\n";
        return 0;
    }
    cout << "YES\n";
    
    count_dfs(0, -1);
    destroy_dfs(0, -1);
}

所感

今回の記事，ほぼ "解説" をしていないな

NoiminのNoise

Tinkoff Internship Warmup Round 2018 and Codeforces Round #475 (Div. 2) D. Destruction of a Tree

問題概要

解法概要

ソースコード

所感