P4395 题解

· · 题解

双倍经验（

Description

给定一棵 n 个点的树，求给每一个点 i 分配一个正整数点权 w_i 使得任意相邻的两个点 i,j 都满足 w_i \ne w_j 且总和最小，输出最小总和。

Solution

设 S_i 为 i 的儿子的集合，f_{i,j} 为 w_i=j 时以 i 为根节点的子树的点权总和的最小值，转移方程如下：

f_{i,j}=j+\sum\limits_{k \in S_i} \min \limits_{p=1,p \ne j}^{\infty}\{f_{k,p}\}

下面对上面这个转移方程进行简要解释，上面这个转移方程也就是说第 i 个点的点权 w_i=j，然后枚举所有 k \in S_i，然后找到最小的 f_{k,p}，但是因为相邻的两个点要满足 w_i \ne w_j，因此要保证 w_i \ne w_k，即 p \ne j。