Submission #1984831

---

Source Code Expand

#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;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:112:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &n);
                        ^
./Main.cpp:116:38: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%d%d", &a, &b);
                                      ^

Judge Result