树形动态规划解决节点着色问题

1. 题目解析与解题思路

这道题目来自2003年波罗的海信息学奥林匹克竞赛（BalticOI），是一道典型的树形动态规划问题。题目要求我们为一棵树的所有节点分配正整数权值，满足相邻节点权值不同的约束条件，同时使整棵树的权值总和最小。

1.1 问题建模

首先我们需要将问题转化为数学模型：

• 给定一棵无向树T=(V,E)，其中V是节点集合，E是边集合
• 需要为每个节点v∈V分配一个颜色c(v)∈Z⁺（正整数）
• 约束条件：对于任意(u,v)∈E，有c(u)≠c(v)
• 目标：最小化∑c(v)，v∈V

1.2 关键观察

通过分析题目，我们可以得出几个重要结论：

1. 颜色数量不需要太多：通过数学证明可以知道，对于任何树结构，最多只需要3种颜色就能满足相邻节点颜色不同的条件
2. 贪心算法不适用：局部最优解不能保证全局最优，必须考虑整棵树的结构
3. 动态规划是合适的解法：树形结构天然适合递归处理，子树的解可以组合成整棵树的解

2. 算法设计与实现

2.1 动态规划状态定义

我们采用树形DP来解决这个问题。定义状态如下：

• f[u][c]：表示以u为根的子树，当u节点选择颜色c时，整棵子树的最小权值和

2.2 状态转移方程

对于每个节点u和可能的颜色c：

1. 初始化：f[u][c] = c（当前节点的权值）
2. 对于u的每个子节点v：
   • 找出v子树中所有颜色≠c的最小权值和min_val
   • f[u][c] += min_val

2.3 算法实现细节

cpp复制#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int INF=0x3f3f3f3f;

int head[N], ver[N*2], net[N*2], tot;
int n, f[N][20], ans=INF;

void add(int a, int b) {
    net[++tot]=head[a];
    head[a]=tot;
    ver[tot]=b;
}

void dfs(int u, int fa) {
    // 初始化：选择颜色1-15的初始代价
    for(int c=1;c