[IAMOI R2] 未送出的花题解

Solution

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

先找找性质。

性质 1

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

怎么证明？反证法。

我们考虑两个结点

u

和

v

（

u\ne v

），假设

u

是

v

的祖先链上的点，如果

u

的盛开度小于

v

，交换

u

，

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)

。

[IAMOI R2] 未送出的花题解

文章操作

Solution

性质 1

性质 2

DP

相关推荐

评论

[IAMOI R2] 未送出的花题解