[POI 03/04 Stage 1] Strings(트리 모델 만들기) (BOJ 1839)

문제가 요구하는 바가 상당히 단순하다.

자력으로 푼 어려운 테크닉이 없는 첫 다이아 4 문제이다!

Ob.1 ) 리프 노드는 노끈의 시작점이다.
Ob.2 ) $($간선 수 - $\sum_v \left \lfloor \frac {\deg(v)}2 \right \rfloor)$가 최소 노끈 개수이다. 각 노드에서 어떻게 연결되는지를 주목하면 알 수 있는 부분.

사용할 노끈의 개수가 고정되었으니, 최소 노끈 길이만 구해주면 된다.
각 서브트리에서 어떤 노끈을 부모 노드에서 더 고려할지 같은 것들을 정해주기 위해 트리 DP를 하면 된다.

근데 이 부분을 그냥 풀 수는 없다는 것을 알 수 있고, 최대 노끈 길이를 파라메트릭 서치를 통해 고정하고서 결정 문제를 풀면 된다.
자식 노드들을 매번 정렬해주면서 풀어야 하므로 $O(n\log^2n)$의 시간 복잡도에 풀 수 있다.

 

 

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>; using ll = long long;
#define rep(i,a,b) for (auto i = (a); i <= (b); ++i)
#define per(i,a,b) for (auto i = (b); i >= (a); --i)
#define all(x) begin(x), end(x)
#define siz(x) int((x).size())
#define Mup(x,y) x = max(x,y)
#define mup(x,y) x = min(x,y)
#define fi first
#define se second
#define dbg(...) fprintf(stderr,__VA_ARGS__)

const int N = 10003;
int n, k, deg[N]; // k := 노끈 수
vector<int> adj[N];
int bound;
bool possible;

template <class T, const int N> struct PURQ {
    T t[2*N]; T (*op)(T,T);
    PURQ(T e, T f(T,T)): op(f) { fill(t,t+2*N,e); }
    void update(int k, T v) {
        assert(0 <= k and k < N);
        for (t[k += N] = v; (k /= 2) >= 1; t[k] = op(t[2*k],t[2*k+1]));
    }
    T query(int a, int b) {
        if (a >= N or b < 0) return 0;
        assert(0 <= a and a < N and 0 <= b and b < N);
        T l = t[0], r = t[0];
        for (a += N, b += N; a <= b; ++a /= 2, --b /= 2) {
            if (a&1) l = op(l,t[a]);
            if (~b&1) r = op(t[b],r);
        }
        return op(l,r);
    }
};
PURQ<int,N> ps(0,[](int x, int y){ return max(x,y); });

int solve(vector<int> &ls) {
    int z = siz(ls);
    vector<int> pi(z);
    pi[0] = -1;
    for (int i = 1; i < z; ++i) {
        pi[i] = z-i;
        ps.update(i,ls[i]+ls[pi[i]]);
    }
    int ml = 1e9;
    for (int i = 0; i < z; ++i) {
        if (max(ps.query(0,i-1),ps.query(i+1,z-1)) <= bound) mup(ml,ls[i]);
        if (i+1 < z) {
            int a = i, b = i+1, d = pi[i+1];
            pi[a] = d, pi[b] = -1, pi[d] = a;
            ps.update(a,ls[a]+ls[d]), ps.update(d,ls[a]+ls[d]);
        }
    }
    return ml;
}

int dfs(int s = 1, int e = 0) {
    vector<int> ls;
    for (auto u : adj[s]) if (u != e) {
        ls.push_back(dfs(u,s));
        if (ls.back() > bound) possible = false;
    }
    if (not empty(ls)) {
        sort(all(ls));
        if (siz(ls)%2 == 0) {
            bool works = true;
            for (int i = 0, j = siz(ls)-1; i < j; i++, j--) {
                if (ls[i]+ls[j] > bound) works = false;
            }
            if (s == 1) {
                if (not works) possible = false;
            }
            if (works) return 1;
            else {
                ls.pop_back();
                int ml = solve(ls);
                if (ml > bound) possible = false;
                return ml+1;
            }
        } else {
            int ml = solve(ls);
            if (ml > bound) possible = false;
            return ml+1;
        }
    }
    return 1;
}

bool valid(int x) {
    bound = x, possible = true;
    dfs();
    return possible;
}

int main() {
    scanf("%d", &n);
    rep(i,2,n) {
        int a, b;
        scanf("%d %d", &a, &b);
        adj[a].push_back(b);
        adj[b].push_back(a);
        deg[a]++, deg[b]++;
    }
    k = n-1;
    rep(v,1,n) k -= deg[v]/2;
    printf("%d ", k);
    int a = 1, b = n, m;
    while (a <= b) {
        m = (a+b)/2;
        if (not valid(m)) a = m+1;
        else b = m-1;
    }
    printf("%d", a);
}