解题思路
本题的目标是在一次调整后最小化全公司员工的层级总和,其中员工的层级定义为该员工到 CEO(员工 1)的简单路径上的边数。
关键观察:
- 初始时,整棵树的层级总和 S 可以通过一次深度优先搜索(DFS)求出。
令 depth[u] 表示员工 u 的层级(CEO 的层级为 0),则 S=∑u=1ndepth[u]。
- 考虑选择任意一名非 CEO 员工 x 并将其所在团队整体划归 CEO 直接领导。
设以 x 为根的子树大小为 sz[x]。操作后,x 将直接连接到 CEO 之下,其层级变为 1;子树内任意员工 u 的新层级变为 1+(depth[u]−depth[x])。