1369: [Baltic2003]Gem

结论

如果一个最优染色方案中包含，那么这棵树至少包含个节点。

证明

显然，如果一个点被染成了，那么它周围一定有点被分别染成了。
设为一个最优方案中根节点被染成了的子树的最小大小。则有

因此，。

做法

暴力DP。

AC代码

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 1e4 + 10, MAXLOGN = 20, INF = 1e8;

int n, fa[MAXN], dp[MAXN][MAXLOGN + 1];
vector<int> edge[MAXN];

void solve(int x) {
    for(vector<int>::iterator i = edge[x].begin(); i < edge[x].end(); i++)
        if(*i != fa[x])
            fa[*i] = x, solve(*i);
    for(int i = 1; i <= MAXLOGN; i++) {
        dp[x][i] = i;
        for(vector<int>::iterator j = edge[x].begin(); j < edge[x].end(); j++)
            if(*j != fa[x]) {
                int tmp = INF;
                for(int k = 1; k <= MAXLOGN; k++)
                    if(k != i) tmp = min(tmp, dp[*j][k]);
                dp[x][i] += tmp;
            }
    }
}

int main() {
    scanf("%d", &n);
    for(int i = 1; i < n; i++) {
        int a, b; scanf("%d%d", &a, &b);
        edge[a].push_back(b); edge[b].push_back(a);
    }
    solve(1);
    int tmp = INF;
    for(int k = 1; k <= MAXLOGN; k++)
        tmp = min(tmp, dp[1][k]);
    printf("%d\n", tmp);
}