• 2024-12-19AT_agc009_d [AGC009D] Uninity 题解
    一道妙妙题。一句话题意:求点分树的高度最小值。给所有点填上一个数表示它子树\(k\),考虑一种填法什么时候满足条件,发现当且仅当任意两对值相同的点之间的路径上存在一个权值更大的点。考虑随便找一个点作为根从叶子节点开始贪心填值,每次选择能填的最小值,发现这样填最终的值的最
  • 2024-11-24AT_agc009_d [AGC009D] Uninity
    这题看完题解后迟迟不下手写代码,因为这道题实在是太厉害了!考虑对于一棵树手玩这个过程,发现如果一个点要作为中间的一个节点,它肯定会挂上周围的所有点所在的树,当然它之后挂的点除外。这事实上是一个点分树的过程,那么该问题就是求最大深度最小的点分树,发现并不好做。好在它刚刚告