题目描述
给出一棵树，要求你为树上的结点标上权值，权值可以是任意的正整数
唯一的限制条件是相临的两个结点不能标上相同的权值，要求一种方案，使得整棵树的总价值最小。
输入格式
先给出一个数字N,代表树上有N个点,N<=10000
下面N-1行,代表两个点相连
输出格式
最小的总权值
输入输出样例
输入 #1
10
7 5
1 2
1 7
8 9
4 1
9 7
5 6
10 2
9 3
输出 #1
14
思路
可以证明（1、2、3、4）就足够赋值了，因为要取最小权值。（证明略，这里有证明）
int h[N], e[M], ne[M], idx; int dp[N][5]; int ans = 2e17; void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; } void dfs(int u, int f) { for (int i = 1; i <= 4; i++) dp[u][i] = i; for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if(j == f) continue; dfs(j, u); for (int k = 1; k <= 4; k++) { int s = 2e17; for (int p = 1; p <= 4; p++) if(k != p) s = min(s, dp[j][p]); dp[u][k] += s; } } } // https://www.luogu.com.cn/problem/P4395 void solve() { int n; cin >> n; memset(h, -1, sizeof h); for (int i = 0; i < n - 1; i++) { int a, b; cin >> a >> b; add(a, b), add(b, a); } dfs(1, 0); for (int i = 1; i <= 4; i++) { ans = min(ans, dp[1][i]); } cout << ans << endl; }
