本题的目标是在一次调整后最小化全公司员工的层级总和,其中员工的层级定义为该员工到 CEO(员工 1)的简单路径上的边数。
关键观察:
depth[u] 表示员工 u 的层级(CEO 的层级为 0),则 S=∑u=1ndepth[u]。sz[x]。操作后,x 将直接连接到 CEO 之下,其层级变为 1;子树内任意员工 u 的新层级变为 1+(depth[u]−depth[x])。在一家公司中,共有 n 名员工,编号为 1 到 n,其中员工 1 为 CEO。公司内部的管理关系构成一棵树,CEO 是树的根节点。若员工 u 是员工 v 的直接上级,则 u 与 v 之间有一条边相连。
定义一名员工的层级为其到 CEO(员工 1)的简单路径所经过的边数。CEO 的层级为 0。
现在 CEO 希望对公司结构进行一次调整,以降低全体员工的层级总和。他可以选择任意一名非 CEO 的员工 x,将以 x 为最高负责人的整个团队(包含 x 及其所有直接或间接的下属)整体划归 CEO 直接领导,即让 x 成为 CEO 的直接下级。在调整之后,CEO 仍为根,其余组织关系保持不变。
请你计算,在最优的选择下,调整后全公司所有员工的层级之和的最小值是多少。
员工总数 n 不超过 2×105,树的边数为 n−1,保证输入构成一棵合法的树。
Scan the QR code below with WeChat to sign in
First-time scan will create your account automatically
请使用微信扫描下方二维码完成注册