1693번: 트리 색칠하기

https://www.acmicpc.net/problem/1693

$O(n\lg n)$

n개의 노드를 색칠하는데 대략 $\log_2 n$ 종류의 색밖에 필요없다.
이를 증명해보자.
$a_i$: 각 색마다 색칠하는 비용이 다를 때, 임의의 그래프에서 i가지 색칠로 최적해를 구하는데 지장이 없는 최대 노드 개수
i번째로 비용이 작은 색을 칠한 노드는 1..i-1번째로 비용이 작은 색을 칠한 노드와 연결되어 있다.
고로, $a_i >= a_1 + a_2 + ... + a_{i-1} + 1$
수학적 귀납법을 통해 $a_i$의 최솟값은 $2^{i-1}$임을 알 수 있다.

이 성질을 이용하여 주어진 그래프를 1번 노드를 root로 하는 rooted tree를 만든 후 dp를 한다.
dp[i][j]: j로 색칠된 i번 노드를 root로 하는 서브트리를 색칠하는데 드는 최소 비용
dp[i][j] = j + sum(k는 노드 i의 자식)(min(l != j)(dp[k][l]))

답은 min(i)(dp[1][i])

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int dp[100001][18], n;
vector<int> adj[100001];
void f(int h, int p) {
    dp[h][0] = 1e9;
    for (int i = 1; i < 18; i++) dp[h][i] += i;
    for (int it : adj[h]) if (it^p) {
        f(it, h);
        int f = 0, s = 0;
        for (int j = 1; j < 18; j++) {
            if (dp[it][s] > dp[it][j]) s = j;
            if (dp[it][f] > dp[it][s]) swap(f, s);
        }
        for (int j = 1; j < 18; j++) dp[h][j] += dp[it][f^j ? f : s];
    }
}
int main() {
    scanf("%d", &n);
    for (int i = 1, x, y; i < n; i++) {
        scanf("%d%d", &x, &y);
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    f(1, 0);
    printf("%d", *min_element(dp[1] + 1, dp[1] + 18));
    return 0;
}