CS Academy 069 D. Cover the Tree

CS Academy

解法

木を最小個数のパスで被覆する問題。選ぶパスは重複して良いことに注意します（もし重複を許さないなら、それはオイラー閉路を適切に構築してそれを出力する問題です）。

とりあえず、葉は必ずパスの端点として選ぶ必要がありそうです。よって(葉の数 $+ 1$) / $2$ 個のパスは必ず必要です。逆に、ある葉ではない頂点を根として考えると、その根を通過するようなパスばかりを選んでいけるならば、この個数で被覆可能です。というわけで、そのような頂点を求めます。

それは明らかに「葉に関する重心」なので（未証明）それを $C$ とします。これは重心を求めるアルゴリズムを葉の数に書き換えると求められます。

葉の重心を選ぶことで次のようにして葉のマッチングさせることができます。まず $C$ から伸びる部分木の中から葉の数が大きい順に $2$ つ選んでその中から適当に $1$ つずつ葉を選んでマッチングをさせる、というプロセスを繰り返します。これは優先度付きキューで効率よく処理できます。

「葉に関するの重心」が、葉になってしまう場合（頂点数 $2$ の木など）の場合分けが面倒なので、頂点倍加のテクニックを使いました。頂点倍加のテクニックとは、与えられた木に対して、すべての辺の途中に新しい頂点を追加することで、（一般的に言う）重心が必ず $1$ 個になるようにするテクニックです。この問題では、これによって葉以外の重心が必ず存在するようにできます。以上でこの問題が解けました。

実装

#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
#include <cassert>
#include <queue>
using namespace std;

int main() {
        int n;
        scanf("%d", &n);
        vector<vector<int>> g(n + n - 1);
        for (int i = 0; i < n - 1; i ++) {
                int a, b;
                scanf("%d %d", &a, &b);
                a --, b --;
                g[a].push_back(n + i);
                g[n + i].push_back(a);
                g[b].push_back(n + i);
                g[n + i].push_back(b);
        }
        n += n - 1; //attention
        vector<int> centroids;
        vector<int> leaves(n);
        int leaves_cnt = 0;
        for (int i = 0; i < n; i ++) {
                if ((int) g[i].size() == 1) {
                        leaves_cnt ++;
                }
        }
        function<void (int, int)> dfs = [&](int u, int prev) {
                leaves[u] = 0;
                bool is_centroid = true;
                for (auto v : g[u]) if (v != prev) {
                        dfs(v, u);
                        leaves[u] += leaves[v];
                        if (leaves[v] > leaves_cnt / 2) is_centroid = false;
                }
                if ((int) g[u].size() == 1) leaves[u] ++;
                if (leaves_cnt - leaves[u] > leaves_cnt / 2) is_centroid = false;
                if ((int) g[u].size() == 1) is_centroid = false;
                if (is_centroid) centroids.push_back(u);
        };
        dfs(0, -1);
        int c = centroids[0];
        vector<vector<int>> leaves_set;
        vector<int> tmp;
        function<void (int, int)> dfs2 = [&](int u, int prev) {
                if ((int) g[u].size() == 1) tmp.push_back(u);
                for (auto v : g[u]) if (v != prev && v != c) {
                        dfs2(v, u);
                }
        };
        for (auto u : g[c]) {
                tmp.clear();
                dfs2(u, -1);
                leaves_set.push_back(tmp);
        }
        swap(leaves_set[0], leaves_set[1]);
        sort(leaves_set.begin(), leaves_set.end(), [&](const vector<int> &a, const vector<int> &b) {
                return (int) a.size() > (int) b.size(); 
        });
        int k = (int) leaves_set.size();
        vector<pair<int, int>> ans;
        priority_queue<pair<int, int>> que; //the number of leaves, index
        for (int i = 0; i < k; i ++) {
                que.push({ (int) leaves_set[i].size(), i });
        }
        while (que.size() >= 2) {
                auto p1 = que.top();
                que.pop();
                auto p2 = que.top();
                que.pop();
                int a = leaves_set[p1.second].back();
                int b = leaves_set[p2.second].back();
                ans.emplace_back(a, b);
                leaves_set[p1.second].pop_back();
                leaves_set[p2.second].pop_back();
                if (p1.first > 1) que.push({ p1.first - 1, p1.second });
                if (p2.first > 1) que.push({ p2.first - 1, p2.second });
        }        
        assert(que.size() <= 1);
        if (que.size() > 0) {
                auto p1 = que.top();
                que.pop();
                ans.emplace_back(leaves_set[p1.second].back(), c);
        }
        printf("%d\n", (int) ans.size());
        for (int i = 0; i < (int) ans.size(); i ++) {
                printf("%d %d\n", ans[i].first + 1, ans[i].second + 1);
        }
}