CS Academy 069 DIV2 D - Cover the Tree

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

• CSA 069 DIV2 D Cover the Tree

---

N 頂点からなるツリーが与えられる。

ツリーのすべての辺を最小本数のパスで覆え。そのようなパスの集合も1つ求めて提示せよ。

• 2 <= N <= 10⁵

---

自明な上界として、ツリーの 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;
        }

  }
}