洛谷 P4395 分析（别看）

科技起源的小号1

2026-10-01 19:26:26

发布于：天津

1阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个最小值

1.2 题目背景、允许、禁止与限制

背景：
有一棵树

允许：
在树上的节点标任意正整数
求整棵树总价值最小

限制
不能连续两个节点都标同样的数

1.3 题目数据范围与猜测

$n \le 10^4 \longrightarrow O(n)$

1.4 一句话概括题意

给定一棵树，对所有节点标注任意正整数（不能为相邻两个节点标注相邻的正整数），求整棵树所有节点标注完成后的最小值

2 题目破题推导

2.1 第一步：数学思想

先考虑一个点标注数字的上界
最优解中，任何一个节点用到的最大颜色编号，基本不会超过 $\lceil log_2 N\rceil + 1$
所以这是一个及其安全的上界
既可以保证最多用到 $14$ 个颜色，也可以保证不超过时间限制

2.2 第二步：大拆小，小组大

接下来比较简单
考虑 $u$ 的每棵子树 $v_i$ ，则 $u$ 的最小花费为

$i(u可能的值)+\sum_{v_i\in u的子树} v_i整棵子树的最小权值(此时应保证v_i的值\neq i)$

3 模型匹配

比较简单的树形dp
状态定义：定义 $dp[u][i]$ 代表将 $u$ 这个节点设置成 $i$ 且 $u$ 的整棵子树已经处理完毕时的最小价值
初始化： $dp[u][i]\leftarrow i$
转移就是枚举点 $u$ 可以放的颜色 $j$ 和 $u$ 的孩子 $v_i$ 可以放的颜色 $k$ ，当 $j\neq k$ 时转移
答案要是 $min\left(dp[root(1)][所有可能颜色] \right)$

4 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;

int n;
const int N = 11111, M = 15 + 10;
vector<int> g[N];
int dp[N][M];
void dfs(int u, int fa){
	for (int i = 1;i <= 15;i++){
		dp[u][i] = i;
	}
	for (int i = 0;i < g[u].size();i++){
		int now = g[u][i];
		if (now == fa){
			continue;
		}
		dfs(now, u);
		for (int j = 1;j <= 15;j++){
			int mn = INT_MAX;
			//
			for (int k = 1;k <= 15;k++){
				if (j == k) continue;
				mn = min(mn, dp[now][k]);
			}
			dp[u][j] += mn;
		}
	}
}

int main(){
	
	cin >> n;
	for (int i = 1;i < n;i++){
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(1, -1);
	int mn = INT_MAX;
	for (int i = 1;i <= 15;i++){
		//
		mn = min(mn, dp[1][i]);
	}
	cout << mn;
	
	return 0;
}