LeetCode-W125

本篇关键词: 树形DP,推导&思维

Q1超过阈值的最少操作数 I

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

一次操作中，你可以删除 nums 中的最小元素。

你需要使数组中的所有元素都大于或等于 k ，请你返回需要的 最少 操作次数。

示例 1：

输入：nums = [2,11,10,1,3], k = 10
输出：3
解释：第一次操作后，nums 变为 [2, 11, 10, 3] 。
第二次操作后，nums 变为 [11, 10, 3] 。
第三次操作后，nums 变为 [11, 10] 。
此时，数组中的所有元素都大于等于 10 ，所以我们停止操作。
使数组中所有元素都大于等于 10 需要的最少操作次数为 3 。

示例 2：

输入：nums = [1,1,2,4,9], k = 1
输出：0
解释：数组中的所有元素都大于等于 1 ，所以不需要对 nums 做任何操作。

示例 3：

输入：nums = [1,1,2,4,9], k = 9
输出：4
解释：nums 中只有一个元素大于等于 9 ，所以需要执行 4 次操作。

提示：

• 1 <= nums.length <= 50
• 1 <= nums[i] <= 109
• 1 <= k <= 109
• 输入保证至少有一个满足 nums[i] >= k 的下标 i 存在。

遍历一遍即可。

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        ans = 0
        for num in nums:
            if num < k: ans += 1
        return ans

Q2超过阈值的最少操作数 II

给你一个下标从 0 开始的整数数组 nums 和一个整数 k 。

一次操作中，你将执行：

• 选择 nums 中最小的两个整数 x 和 y 。
• 将 x 和 y 从 nums 中删除。
• 将 min(x, y) * 2 + max(x, y) 添加到数组中的任意位置。

**注意，**只有当 nums 至少包含两个元素时，你才可以执行以上操作。

你需要使数组中的所有元素都大于或等于 k ，请你返回需要的 最少 操作次数。

示例 1：

输入：nums = [2,11,10,1,3], k = 10
输出：2
解释：第一次操作中，我们删除元素 1 和 2 ，然后添加 1 * 2 + 2 到 nums 中，nums 变为 [4, 11, 10, 3] 。
第二次操作中，我们删除元素 3 和 4 ，然后添加 3 * 2 + 4 到 nums 中，nums 变为 [10, 11, 10] 。
此时，数组中的所有元素都大于等于 10 ，所以我们停止操作。
使数组中所有元素都大于等于 10 需要的最少操作次数为 2 。

示例 2：

输入：nums = [1,1,2,4,9], k = 20
输出：4
解释：第一次操作后，nums 变为 [2, 4, 9, 3] 。
第二次操作后，nums 变为 [7, 4, 9] 。
第三次操作后，nums 变为 [15, 9] 。
第四次操作后，nums 变为 [33] 。
此时，数组中的所有元素都大于等于 20 ，所以我们停止操作。
使数组中所有元素都大于等于 20 需要的最少操作次数为 4 。

提示：

• 2 <= nums.length <= 2 * 105
• 1 <= nums[i] <= 109
• 1 <= k <= 109
• 输入保证答案一定存在，也就是说一定存在一个操作序列使数组中所有元素都大于等于 k 。

使用堆模拟即可

class Solution:
    def minOperations(self, nums: List[int], k: int) -> int:
        heapq.heapify(nums)
        ans = 0
        while len(nums) >= 2 and nums[0] < k:
            poll1, poll2 = heapq.heappop(nums), heapq.heappop(nums)
            heapq.heappush(nums, min(poll1, poll2) * 2 + max(poll2, poll1))
            ans += 1
        return ans

Q3 在带权树网络中统计可连接服务器对数目

给你一棵无根带权树，树中总共有 n 个节点，分别表示 n 个服务器，服务器从 0 到 n - 1 编号。同时给你一个数组 edges ，其中 edges[i] = [ai, bi, weighti] 表示节点 ai 和 bi 之间有一条双向边，边的权值为 weighti 。再给你一个整数 signalSpeed 。

如果两个服务器 a ，b 和 c 满足以下条件，那么我们称服务器 a 和 b 是通过服务器 c 可连接的 ：

• a < b ，a != c 且 b != c 。
• 从 c 到 a 的距离是可以被 signalSpeed 整除的。
• 从 c 到 b 的距离是可以被 signalSpeed 整除的。
• 从 c 到 b 的路径与从 c 到 a 的路径没有任何公共边。

请你返回一个长度为 n 的整数数组 count ，其中 count[i] 表示通过服务器 i 可连接 的服务器对的 数目 。

示例 1：

输入：edges = [[0,1,1],[1,2,5],[2,3,13],[3,4,9],[4,5,2]], signalSpeed = 1
输出：[0,4,6,6,4,0]
解释：由于 signalSpeed 等于 1 ，count[c] 等于所有从 c 开始且没有公共边的路径对数目。
在输入图中，count[c] 等于服务器 c 左边服务器数目乘以右边服务器数目。

示例 2：

输入：edges = [[0,6,3],[6,5,3],[0,3,1],[3,2,7],[3,1,6],[3,4,2]], signalSpeed = 3
输出：[2,0,0,0,0,0,2]
解释：通过服务器 0 ，有 2 个可连接服务器对(4, 5) 和 (4, 6) 。
通过服务器 6 ，有 2 个可连接服务器对 (4, 5) 和 (0, 5) 。
所有服务器对都必须通过服务器 0 或 6 才可连接，所以其他服务器对应的可连接服务器对数目都为 0 。

提示：

• 2 <= n <= 1000
• edges.length == n - 1
• edges[i].length == 3
• 0 <= ai, bi < n
• edges[i] = [ai, bi, weighti]
• 1 <= weighti <= 106
• 1 <= signalSpeed <= 106
• 输入保证 edges 构成一棵合法的树。

树形DP。由于数据范围为1000,可以写一个$O(n^2)$的算法。那么就把所有的点遍历一次。对于一个点e的两个子节点a和b而言，假设e通过a可以到达x个点，e通过b可以到达y个节点，那么e的总连接就是x * y个节点。对于单条a或单条b的搜索是一个累加的过程，如果e有多个子节点的话，就得要用到一个边加边乘的技巧，这个技巧也是很常见的。

class Solution:
    def countPairsOfConnectableServers(self, edges: List[List[int]], signalSpeed: int) -> List[int]:
        n = len(edges) + 1
        f = [0] * n
        g = [[] for _ in range(n)]
        for x, y, v in edges:
            g[x].append((y, v))
            g[y].append((x, v))

        def dfs2(e: int, pa: int, d: int) -> int:
            ans = (d % signalSpeed == 0)
            for u in g[e]:
                ee, k = u[0], u[1]
                if ee != pa:
                    ans += dfs2(ee, e, d + k)
            return ans

        def dfs(e: int, pa: int) -> int:
            s = 0
            ans = 0
            for u in g[e]:
                ee, k = u[0], u[1]
                if ee != pa:
                    v = dfs2(ee, e, k)
                    ans += s * v
                    s += v
            return ans
        for i in range(n): f[i] = dfs(i, -1)
        return f

Q4最大节点价值之和

给你一棵 n 个节点的 无向 树，节点从 0 到 n - 1 编号。树以长度为 n - 1 下标从 0 开始的二维整数数组 edges 的形式给你，其中 edges[i] = [ui, vi] 表示树中节点 ui 和 vi 之间有一条边。同时给你一个 正 整数 k 和一个长度为 n 下标从 0 开始的 非负 整数数组 nums ，其中 nums[i] 表示节点 i 的 价值 。

Alice 想 最大化 树中所有节点价值之和。为了实现这一目标，Alice 可以执行以下操作 任意 次（包括 0 次）：

• 选择连接节点

  u

  和

  v

  的边

  [u, v]

  ，并将它们的值更新为：

  • nums[u] = nums[u] XOR k
  • nums[v] = nums[v] XOR k

请你返回 Alice 通过执行以上操作 任意次 后，可以得到所有节点 价值之和 的 最大值 。

示例 1：

输入：nums = [1,2,1], k = 3, edges = [[0,1],[0,2]]
输出：6
解释：Alice 可以通过一次操作得到最大价值和 6 ：
- 选择边 [0,2] 。nums[0] 和 nums[2] 都变为：1 XOR 3 = 2 ，数组 nums 变为：[1,2,1] -> [2,2,2] 。
所有节点价值之和为 2 + 2 + 2 = 6 。
6 是可以得到最大的价值之和。

示例 2：

输入：nums = [2,3], k = 7, edges = [[0,1]]
输出：9
解释：Alice 可以通过一次操作得到最大和 9 ：
- 选择边 [0,1] 。nums[0] 变为：2 XOR 7 = 5 ，nums[1] 变为：3 XOR 7 = 4 ，数组 nums 变为：[2,3] -> [5,4] 。
所有节点价值之和为 5 + 4 = 9 。
9 是可以得到最大的价值之和。

示例 3：

输入：nums = [7,7,7,7,7,7], k = 3, edges = [[0,1],[0,2],[0,3],[0,4],[0,5]]
输出：42
解释：Alice 不需要执行任何操作，就可以得到最大价值之和 42 。

提示：

• 2 <= n == nums.length <= 2 * 104
• 1 <= k <= 109
• 0 <= nums[i] <= 109
• edges.length == n - 1
• edges[i].length == 2
• 0 <= edges[i][0], edges[i][1] <= n - 1
• 输入保证 edges 构成一棵合法的树。

本场的压轴题。两种思考的方式。首先来看树形DP。$f[i][0]$代表以i为根节点且根节点异或了偶数次的和的最大值，$f[i][1]$代表以i为根节点且根节点异或了奇数次的和的最大值。考虑如何转移。对于节点i我们遍历每一条边，注意这里是一个累加的过程，因为是求和。$f[i][0] = \max(pre(f[i][0]) + \max(nxt[0], nxt[1]), pre(f[i][1]) + \max(nxt[0] + ((nums[e] \oplus k) - nums[e]), nxt[1] + (nums[e] - (nums[e] \oplus k))))$

$f[i][1] = \max(pre(f[i][1]) + \max(nxt[0], nxt[1]), pre(f[i][0]) + \max(nxt[0] + ((nums[e] \oplus k) - nums[e]), nxt[1] + (nums[e] - (nums[e] \oplus k))))$

遍历每个点前只能是异或0次初始$f[i][0] = 0, f[i][1] = -\inf$。

class Solution:
    def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int:
        g = [[] for _ in nums]
        for x, y in edges:
            g[x].append(y)
            g[y].append(x)

        def dfs(x: int, fa: int) -> List[int]:  # 返回的是当前节点异或奇数或异或偶数次
            ret = [0, -10 ** 10]  # 这里的-10 ** 10代表刚开始根本不可能出现异或奇数次，只能是0次
            for e in g[x]:
                if e != fa:
                    a, b = ret[0], ret[1]
                    nxt_a, nxt_b = dfs(e, x)
                    ret[0] = max(a + max(nxt_a, nxt_b),
                                 b + max(nxt_a + ((nums[e] ^ k) - nums[e]), nxt_b + (nums[e] - (nums[e] ^ k))))
                    ret[1] = max(b + max(nxt_a, nxt_b),
                                 a + max(nxt_a + ((nums[e] ^ k) - nums[e]), nxt_b + (nums[e] - (nums[e] ^ k))))
            ret[0] += nums[x]
            ret[1] += (nums[x] ^ k)
            return ret

        return max(dfs(0, -1))

继续深挖本题的性质，因为可以操作任意次，那么首先考虑任意一对点(因为是树，肯定是联通的)，假设这条边是$a->b->c->d$，当选择按照顺序两两依次进行操作时，最后只剩下首尾节点得到了有效异或。这也就说明我们可以在树中选择任意两个有效节点进行异或操作，进一步推广，我们可以选择偶数个节点进行异或操作，因为操作就是0，操作就是两个，那么最后的有效异或肯定是偶数个。那么问题就转换成了，在数组中挑选偶数个数进行异或操作，最后求和最大值。状态机动态规划可以解决，f[i]表示前i个数操作了偶数次的和，g[i]表示前i个数操作了奇数次的和，f[0] = nums[0],g[0] = nums[0] ^ k,f[i] = max(nums[i] + f[i - 1], (nums[i] ^ k) + g[i - 1]),g[i] = max(nums[i] + g[i - 1], (nums[i] ^ k) + f[i - 1])

class Solution:
    def maximumValueSum(self, nums: List[int], k: int, edges: List[List[int]]) -> int:
        n = len(nums)
        f, g = [0] * n, [0] * n
        f[0] = nums[0]
        g[0] = nums[0] ^ k
        for i in range(1, n):
            f[i] = max(g[i - 1] + (k ^ nums[i]), f[i - 1] + nums[i])
            g[i] = max(g[i - 1] + nums[i], f[i - 1] + (nums[i] ^ k))
        return f[-1]