"给树染色问题的算法解题指南"
在给定的题目中,我们面临的是一个经典的树染色问题,这是一个典型的图论与动态规划相结合的问题。树的节点有编号和权值,染色的过程需要遵循一定的规则,并且每次染色都有代价。目标是最小化染色的总代价。
### 问题描述
- **节点**:一棵树有 n 个节点,编号从 1 到 n。
- **权值**:每个节点 i 有一个权值 A[i],表示该节点染色的代价。
- **染色规则**:根节点 R 可以随时染色;其他节点在其父节点被染色后才能染色。
- **代价**:第 i 次染色的代价为 T × A[i],T 为当前染色的次数。
- **输入**:包括 n(节点数)、R(根节点编号),所有节点的权值,以及父子节点的关系。
- **输出**:最小的染色总代价。
### 输入样例分析
样例中,有 5 个节点,根节点是 1。节点的权值分别为 12、12、12、4、5。根据父子节点关系构建树的结构。
### 解题思路
- **参考答案** 使用了动态规划的方法,结合图的遍历来解决此问题。
- **节点结构**:定义 `Node` 结构体,包含节点的父节点(p),子节点数量(s),权值(v)以及平均代价(avg)。
- **初始化**:遍历所有节点,计算每个节点的初始平均代价(等于其权值),并将根节点的平均代价设为 0。
- **构建树**:读取父子节点关系,构建树的邻接表。
- **动态规划**:通过循环找到当前未染色且平均代价最大的子节点,将其染色并更新其父节点的平均代价。这个过程不断进行,直到所有节点都被染色。
- **总代价**:在染色过程中累加所有节点的染色代价,得到最小总代价。
### 动态规划详解
1. 初始化:将所有节点的初始平均代价设置为权值,根节点的平均代价设为 0。
2. 遍历树:每次选择一个未染色的子节点 p,其平均代价最大。染色这个节点会增加其父节点的平均代价(father_avg += nodes[p].v/nodes[father].s)。
3. 更新总代价:每次染色都要加上当前染色的代价 (T * A[i]),T 是当前的染色次数,即已染色节点的数量。
4. 继续遍历,直到所有节点都被染色。
5. 最终得到的总代价即为最小染色总代价。
### 时间复杂度与空间复杂度
- **时间复杂度**:O(n),其中 n 是节点数,因为每个节点最多被访问一次。
- **空间复杂度**:O(n),用于存储树的结构和动态规划过程中的状态。
这个解题策略充分利用了树的结构,通过动态调整子节点的染色顺序来优化总代价。在实际编程时,需要注意边界条件和特殊情况的处理,以确保算法的正确性。