CF1153D神仙DP
题目
给出一颗有根树,在每个非叶子节点都有一个属性:
- $max$ : 在所有儿子的权值中取最大值
- $min$ : 在所有儿子的权值中取最小值
假设这颗树有k个叶子结点,现在你需要对这k个叶子结点赋值[1,k]且两两互不相同。问根结点的最大值可以是多少。
求解
很难用数值直接处理,我们使用排名进行树形dp,排名第1的权值即为k,最低排名的权值即为1。
令$dp_u$表示以u为根的子树的所有叶节点中,结点u可以取得的最大值的排名,也即能得的最小排名。
如果u为:
- 叶节点:$dp_u=1$
- $max$结点:$dp_u=min(dp_v)$
- $min$结点:$dp_u=\sum dp_v$
最后答案就为$k+1-dp_1$。
代码:
1 |
|