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

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

CS Academy 069 DIV2 D - Cover the Tree

本番はツリーDPな方向性に走って詰め切れなかったん。ひょっとしたらツリーDPでも解けるのかもしれないが復元が大変そうなん...

ツリーの重心に関する理解が足りてないことがわかったので勉強してまとめたのん。
ツリーの重心分解 (木の重心分解) の図解 - Qiita

CSA 069 DIV2 D Cover the Tree


N 頂点からなるツリーが与えられる。ツリーのすべての辺を最小本数のパスで覆え。そのようなパスの集合も1つ求めて提示せよ。

  • 2 <= N <= 105

自明な上界として、ツリーの leaf / 2 本のパスは絶対に必要である。
が、それで実際にすべての辺を覆えることが、ツリーの重心を考えるとわかる。
ただしここでいう重心とは、「その頂点を取り除いてできるどの部分木の leaf の個数も、元のグラフの leaf の個数の半分以下」になるような頂点のことである。

パスの端点は leaf だけ考えれば十分で、パスを作るときは必ず重心を通るようにすればよい。
それを実現するためには、subtrees のうち、常にサイズの大きい 2 つからとっていけばよい。

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;

const int MAX_V = 210000;
int N;
vector<int> tree[MAX_V];

bool isLeaf[MAX_V];
int sizeLeaf[MAX_V];

int center = -1;
void FindCentroid(int v, int size, int p = -1) {
    sizeLeaf[v] = 0;
    bool isCentroid = true;
    for (auto ch : tree[v]) {
        if (ch == p) continue;
        FindCentroid(ch, size, v);
        if (sizeLeaf[ch] > size / 2) isCentroid = false;
        sizeLeaf[v] += sizeLeaf[ch];
    }
    if (isLeaf[v]) ++sizeLeaf[v];
    if (size - sizeLeaf[v] > size / 2) isCentroid = false;
    if (isCentroid) center = v;
}

map<int, vector<int> > subtrees;
void rec(int v, int r, int p) {
    for (auto ch : tree[v]) {
        if (ch == p) continue;
        rec(ch, r, v);
    }
    if (isLeaf[v]) subtrees[r].push_back(v);
}

typedef pair<int, int> pint;
int main() {
    while (cin >> N) {
        for (int i = 0; i < MAX_V; ++i) tree[i].clear();
        for (int i = 0; i < N - 1; ++i) {
            int a, b;
            cin >> a >> b;
            --a, --b;
            tree[a].push_back(b);
            tree[b].push_back(a);
        }

        if (N == 2) {
            cout << 1 << endl;
            cout << "1 2" << endl;
            return 0;
        }

        int leafnum = 0;
        int root = 0;
        memset(isLeaf, 0, sizeof(isLeaf));
        for (int i = 0; i < N; ++i) {
            if (tree[i].size() == 1) isLeaf[i] = true, ++leafnum;
            else root = i;
        }
        FindCentroid(root, leafnum);

        subtrees.clear();
        priority_queue<pint> que;
        for (auto adj : tree[center]) {
            rec(adj, adj, center);
            que.push(pint(subtrees[adj].size(), adj));
        }

        vector<pint> res;
        while (!que.empty()) {
            pint fi = que.top();
            que.pop();

            if (que.empty()) {
                res.push_back(pint(subtrees[fi.second].back(), center));
                break;
            }

            pint se = que.top();
            que.pop();

            int fileaf = subtrees[fi.second].back();
            subtrees[fi.second].pop_back();

            int seleaf = subtrees[se.second].back();
            subtrees[se.second].pop_back();

            res.push_back(pint(fileaf, seleaf));

            if (subtrees[fi.second].size()) {
                que.push(pint((int)subtrees[fi.second].size(), fi.second));
            }
            if (subtrees[se.second].size()) {
                que.push(pint((int)subtrees[se.second].size(), se.second));
            }
        }

        cout << res.size() << endl;
        for (int i = 0; i < res.size(); ++i) {
            cout << res[i].first + 1 << " " << res[i].second + 1 << endl;
        }

  }
}