375

375-D 题目大意 给定一颗\(n\)个节点的树，根节点为\(1\)，每个节点都有一个颜色\({c}_{i}\) 给定\(q\)次询问： \((x,k):\)询问在以\(x\)为根的子树中出现次数\({\ge}k\)的颜色数量 Solution 首先考虑一般暴力的做法，将所有询问离线下来，对整个树 ......

使用差分的思想进行解决 class Solution: def countTestedDevices(self, batteryPercentages: List[int]) -> int: diff = 0 for x in batteryPercentages: if x > diff: dif ......

看错题看成只能交换相邻节点颜色了/fn 每次操作交换两个节点颜色，可以转化为统计最终合法颜色序列相比开始，最少有多少个红点变成黑点。 可以考虑一个类似树形 dp 的过程，对于每个节点我们钦定下它会被哪个节点“笼罩”，同时由于黑点数量有限，我们还需要记录下子树内已经用了多少个黑点。 设“笼罩”节点 \ ......