[IAMOI R2] 未送出的花 题解

· · 题解

Solution

我们确定一种盛开度的方案后，将每个点的美丽度算出来，从大到小排序，就是这种盛开度方案的结果。

先找找性质。

性质 1

观察样例，可以发现父亲的盛开度总是大于儿子的盛开度。

怎么证明？反证法。

我们考虑两个结点 u 和 v（u\ne v），假设 u 是 v 的祖先链上的点，如果 u 的盛开度小于 v ，交换 u，v 的盛开度一定会使结果不劣。

因为交换后：

那么最后的美丽度集合一定不劣。

性质 2

由性质 1 可知，每一个点的美丽度是其祖先链中位数的点的盛开度。

就是说，每一个点的美丽度，直接由中位数祖先的盛开度决定。

那么，每一个点盛开度，所影响到美丽度的点的数量也是一定的。

DP

定义树的拓扑序为：对树的所有节点进行排列，使得每个节点都出现在其父节点之后的排列。

由性质 1，最优方案是按照树的某种拓扑序，从大到小给定盛开度。

记每一个点所能影响到的点数量为 cnt_i。

答案可以表述为：找到一个最大的 d，使得存在一个长度为 n-d+1 的拓扑序前缀，使得其能影响到的点总数量大于等于 k。

（即找到一个最大的 d，使得存在一个拓扑序 \{s_i\}，有 \sum_{i=1}^{n-d+1}cnt_{s_i}\ge k。）

考虑树形 DP（或者说是树上背包）。

设 f_{cu,j} 为 cu 子树内，长度为 j 的拓扑序前缀，所能影响点的数量的最大值。

对于每一个 x\in son_{cu}：

f_{cu,k}\overset{\min}{\leftarrow}\min_{i+j=k\land i,j\ge 1}f_{cu,i}+f_{x,j}

初始条件是 f_{cu,1}=cnt_{cu}。

时间复杂度为树形背包复杂度为 O(n^2)。