题目大意:
- 给定一棵 nn 个点的树，其中每个点可能是黑色或白色。
- 一个点的高度定义为其距离最近黑色节点的距离。
- 你初始在 ii 号节点上，势能为 00，可以做以下两种操作：
- 向高度更小的相邻节点移动，增加 11 的势能。
- 向高度相同的相邻节点移动，减少 11 的势能，这个操作只能在你的势能 \geq 1≥1 时执行。
- 对于 i=1,2,\cdots, ni=1,2,⋯,n，求出你能做的操作数的最大值。
- n\leq 2\times 10^5n≤2×105。
思路:
- 首先通过BFS将每一个点的高度给求出来
- 找规律,通过规律来贪心, 发现 每一个高度为 h 的点,一定可以走 h步, 在加上h的势能, 这个点可以到一个平台(h=b) (就可以将那部分h-b的势能转化为操作数)
- 于是就贪心的看 每一个点 所到的平台的高度最小是哪里就行了
- 继续找规律, 发现这个平台(几个相同高度的点想连接在一起) ,一个要组合成一个平台(高度=h),就至少需要花费 2*h个点. 不同高度的平台个数最多为根号n,
- 证明: n个不同高度的平台需要的点数为: 2*(1+2+3+4+5+6+......)=n*(n+1); 所以 不同高度的平台个数最多为根号n,
- 然后从平台高度入手,看哪些点可以到他, 由于是树, 边权也不奇怪, 传递也是有规律, 就多源 bfs层数, 同层 +1, 不然就-1, 点权值<=0,即可
标签：Mountain,势能,Snowy,平台,高度,节点,根号,贪心 From： https://www.cnblogs.com/Lamboofhome/p/16812975.html