Easy树
题意
给出一棵树，要求你为树上的结点标上权值，权值可以是任意的正整数
唯一的限制条件是相临的两个结点不能标上相同的权值，要求一种方案，使得整棵树的总价值最小。
思路
有一个错误的贪心思路，即把树染色，较多的填 \(1\)，较少的填 \(2\)。
这种思路可以被两个中心连在一起的菊花图 Hack 掉。
考虑 dp。定义 \(dp_{i,j}\) 表示以 \(i\) 为根的子树中，\(i\) 填 \(j\) 时的最小权值。
初始状态 \(dp_{i,j}=j\)，转移方程：
\[dp_{i,j}=\sum_{v\in s_i}\min_{k\ne j} dp_{v,k} \]\(j\) 的上界大约是 \(20\) 左右。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 5;
int n, dp[N][21];
vector <int> E[N];
void dfs(int x, int fa) {
for (int i = 1; i <= 20; i ++)
dp[x][i] = i;
for (auto y : E[x]) {
if (y == fa) continue;
dfs(y, x);
for (int j = 1; j <= 20; j ++) {
int minn = 1e9;
for (int k = 1; k <= 20; k ++) {
if (k != j) minn = min(minn, dp[y][k]);
}
dp[x][j] += minn;
}
}
}
int main() {
cin >> n;
for (int i = 1, u, v; i < n; i ++) {
cin >> u >> v;
E[u].push_back(v);
E[v].push_back(u);
}
dfs(1, 0);
int ans = 1e9;
for (int i = 1; i <= 20; i ++)
ans = min(ans, dp[1][i]);
cout << ans << "\n";
return 0;
}