Atcoder Regular Contest 088 F. Christmas Tree

Atcoder Regular Contest 088 F. Christmas Tree

F - Christmas Tree

感想

木をいくつかのパスで被覆する、よくありそうな問題です。CSA Flip the Edgesに似ています。

解法

まずパスの両端の次数は奇数でそれ以外は偶数である（それはそう）という性質から、グラフの奇数次の頂点は一つ以上のパスの端っこの点になるはずなので、$A$ の必要条件として、$ A \geq $ (奇数次の頂点数 / $2$ ) が言えます。もう少し考えると、$ A =$ (奇数次の頂点数 / $2$) が言えます。これは葉から順にパスを作っていくことを考えれば良いです。

これで $A$ が求められたので、次に $B$ を考えていきいます。まず長さ $B$ "以下"のパスを使えるという条件から、二分探索をすればよさそうということが自然にわかるので、それをします。

長さを固定したあとはふつうに木dpをやります。すなわち、$dp(u) = $ (ある部分木以下を長さ $x$ 以下のパスだけで被覆していて、かつ上に伸ばすパスの最小の長さ) とすればよいです。これを偶奇に応じて適切に遷移させればよいです。

しかしこれだと上に伸ばすパスをどのように選ぶかという問題が残っていて、愚直にやると最悪ケースで $O(n^2)$ になるのでダメです。しかしこれは上に伸ばすパスが長ければ長いほど、下の部分木で条件を満たすのが容易になるという性質から、二分探索で決めることができます。

以上で解けました。

実装

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

bool check(const vector<int> &tmp, int x) {
        assert((int) tmp.size() % 2 == 0);
        int bg = 0, ed = tmp.size() - 1;
        bool res = true;
        while (bg < ed) {
                if (tmp[bg] + tmp[ed] > x) {
                        res = false;
                }
                bg ++, ed --;
        }
        return res;
}

bool ok(int x, int n, const vector<vector<int>> &g) {
        vector<int> dp(n);
        function<bool (int, int)> dfs = [&](int u, int prev) {
                vector<int> child;
                for (auto v : g[u]) if (v != prev) {
                        if (!dfs(v, u)) return false;
                        if (dp[v] + 1 > x) return false;
                        child.push_back(dp[v] + 1);
                }
                if (child.empty()) {
                        dp[u] = 0;
                        return true;
                }
                sort(child.begin(), child.end());
                int deg = g[u].size();
                for (int i = 0; i < child.size(); i ++) {
                        if (child[i] > x) {
                                return false;
                        }
                }
                if (u == 0) {
                        if (deg & 1) {
                                child.pop_back();
                                if (!check(child, x)) {
                                        return false;
                                }
                        } else {
                                if (!check(child, x)) {
                                        return false;
                                }
                        }
                        return true;
                }
                if (deg & 1) {
                        vector<int> tmp;
                        tmp = child;
                        if (check(tmp, x)) {
                                dp[u] = 0;
                        } else {
                                int lb = 0, ub = child.size();
                                while (ub - lb > 0) {
                                        tmp.clear();
                                        int mid = (lb + ub) / 2;
                                        for (int i = 0; i < child.size(); i ++) {
                                                if (i != mid) {
                                                        tmp.push_back(child[i]);
                                                }
                                        }
                                        tmp.pop_back();
                                        if (check(tmp, x)) {
                                                ub = mid;
                                        } else {
                                                lb = mid + 1;
                                        }
                                }
                                if (ub == child.size()) {
                                        return false;
                                }
                                dp[u] = child[ub];
                        }
                } else {
                        vector<int> tmp;
                        int lb = 0, ub = child.size();
                        while (ub - lb > 0) {
                                tmp.clear();
                                int mid = (lb + ub) / 2;
                                for (int i = 0; i < child.size(); i ++) {
                                        if (i != mid) {
                                                tmp.push_back(child[i]);
                                        }
                                }
                                if (check(tmp, x)) {
                                        ub = mid;
                                } else {
                                        lb = mid + 1;
                                }
                        }
                        if (ub == child.size()) {
                                return false;
                        }
                        dp[u] = child[ub];
                }
                return true;
        };
        bool res = dfs(0, -1);
        return res;
}

int main() {
        int n;
        scanf("%d", &n);
        vector<vector<int>> g(n);
        for (int i = 0; i < n - 1; i ++) {
                int a, b;
                scanf("%d%d", &a, &b);
                a --, b --;
                g[a].push_back(b);
                g[b].push_back(a);
        }
        int a = 0;
        for (int i = 0; i < n; i ++) {
                if ((int) g[i].size() & 1) a ++;
        }
        assert(a % 2 == 0);
        a /= 2;
        int lb = 0, ub = n;
        while (ub - lb > 1) {
                int mid = (lb + ub) / 2;
                if (ok(mid, n, g)) {
                        ub = mid;
                } else {
                        lb = mid;
                }
        }
        printf("%d %d\n", a, ub);
        return 0;
}