题目
There is an undirected connected tree with n nodes labeled from 0 to n - 1 and n - 1 edges.
You are given a 0-indexed integer array nums of length n where nums[i] represents the value of the ith node. You are also given a 2D integer array edges of length n - 1 where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree.
Remove two distinct edges of the tree to form three connected components. For a pair of removed edges, the following steps are defined:
- Get the XOR of all the values of the nodes for each of the three components respectively.
- The difference between the largest XOR value and the smallest XOR value is the score of the pair.
- For example, say the three components have the node values:
[4,5,7],[1,9], and[3,3,3]. The three XOR values are4 ^ 5 ^ 7 = 6,1 ^ 9 = 8, and3 ^ 3 ^ 3 = 3. The largest XOR value is8and the smallest XOR value is3. The score is then8 - 3 = 5.
Return the minimum score of any possible pair of edge removals on the given tree.
Example 1:
Input: nums = [1,5,5,4,11], edges = [[0,1],[1,2],[1,3],[3,4]] Output: 9 Explanation: The diagram above shows a way to make a pair of removals. - The 1st component has nodes [1,3,4] with values [5,4,11]. Its XOR value is 5 ^ 4 ^ 11 = 10. - The 2nd component has node [0] with value [1]. Its XOR value is 1 = 1. - The 3rd component has node [2] with value [5]. Its XOR value is 5 = 5. The score is the difference between the largest and smallest XOR value which is 10 - 1 = 9. It can be shown that no other pair of removals will obtain a smaller score than 9.
Example 2:
Input: nums = [5,5,2,4,4,2], edges = [[0,1],[1,2],[5,2],[4,3],[1,3]] Output: 0 Explanation: The diagram above shows a way to make a pair of removals. - The 1st component has nodes [3,4] with values [4,4]. Its XOR value is 4 ^ 4 = 0. - The 2nd component has nodes [1,0] with values [5,5]. Its XOR value is 5 ^ 5 = 0. - The 3rd component has nodes [2,5] with values [2,2]. Its XOR value is 2 ^ 2 = 0. The score is the difference between the largest and smallest XOR value which is 0 - 0 = 0. We cannot obtain a smaller score than 0.
Constraints:
n == nums.length3 <= n <= 10001 <= nums[i] <= 108edges.length == n - 1edges[i].length == 20 <= ai, bi < nai != biedgesrepresents a valid tree.
思路&代码
题目大意，在一棵树（注意不是二叉树）里面去掉两条边，将树分为三部分，每部分内分别对求每个值求xor，得到三个值xor1,xor2,xor3，求max(xor1,xor2,xor3) – min(xor1,xor2,xor3)的最小值。
提到位运算，先来复习下xor的性质。
0 xor 0 = 0, 1 xor 1 = 0, 0 xor 1 = 1, 1 xor 0 = 1
a xor b = c，则有 a = c xor b, b = c xor a
同理(a1, a2, …, an) xor (b1, b2, …, bn) = (c1, c2, …, cn)，则有(a1, a2, …, an) = (c1, c2, …, cn) xor (b1, b2, …, bn)
回到题目，题目求的是最值问题，xor和最值是没有特别多的性质的，再看len(nums)<=1000，可以考虑穷举法，每个部分的xor可以利用上面的性质减少重复计算。
那么我们的思路如下。
for ea, eb in permuate(所有边):
a, b, c = 三部分的xor
score = max(a, b, c) – min(a, b, c)
关键在于，怎么求分成的三部分的异或值。仔细想下我们会发现，其实只会有以下两种情况。
case1，一条边在以另一条边的子节点形成的子树上。
case2，两条边都不在彼此的子树上。
对于case1，三部分的xor值分别为X（eb子树），X（ea子树）xor X（eb子树），X（root） xor X（ea子树）。
对于case2，三部分的xor值分别为X（ea子树），X（ea子树），X（root） xor X（ea子树）xor X(eb子树）。
其中，X为子树下面所有节点的异或值。
OK，思路很清晰了，下面直接上代码。
import collections
class Solution(object):
def minimumScore(self, nums, edges):
"""
:type nums: List[int]
:type edges: List[List[int]]
:rtype: int
"""
m_edge = collections.defaultdict(list)
for a, b in edges:
m_edge[a].append(b)
m_edge[b].append(a)
root = None
for a in m_edge:
if len(m_edge[a]) == 1:
root = a
break
xor_map = {}
descendant_map = {}
def _travel(r, father):
children, xor = set(m_edge[r]), nums[r]
if father is not None:
children.remove(father)
for c in m_edge[r]:
if c == father:
continue
c_, x_ = _travel(c, r)
children.update(c_)
xor ^= x_
xor_map[r] = xor
descendant_map[r] = children
return children, xor
def _get_child(e):
a, b = e
if a in descendant_map and b in descendant_map[a]:
return b
else:
return a
# ea is child of eb
def _is_descendant(ea, eb):
bc, ac = _get_child(eb), _get_child(ea)
return bc in descendant_map and ac in descendant_map[bc]
_travel(root, None)
ret = None
for i in range(len(edges)):
for j in range(i + 1, len(edges)):
ea, eb = edges[i], edges[j]
a, b, c = 0, 0, 0
if _is_descendant(ea, eb):
eac, ebc = _get_child(ea), _get_child(eb)
a = xor_map[eac]
b = xor_map[ebc] ^ a
c = xor_map[root] ^ xor_map[ebc]
elif _is_descendant(eb, ea):
eac, ebc = _get_child(ea), _get_child(eb)
a = xor_map[ebc]
b = xor_map[eac] ^ a
c = xor_map[root] ^ xor_map[eac]
else:
eac, ebc = _get_child(ea), _get_child(eb)
a, b = xor_map[eac], xor_map[ebc]
c = xor_map[root] ^ a ^ b
score = max(a, b, c) - min(a, b, c)
ret = score if ret is None else min(score, ret)
return ret提交上去，贴地过，翻了翻讨论区和提交记录，大家的思路简直一模一样，于是懒得优化了=。=
就事论事，这种时间比较紧的题，python其实略吃亏，很容易一手滑就超时的。事后再看看，优化的点应该是line21的那个len(nums)个set，改成len(nums) * len(nums)的01矩阵会好很多。
收工！
——此处是内容的分割线——
除非注明，否则均为广陌原创文章，转载必须以链接形式标明本文链接
本文链接：https://www.utopiafar.com/2022/06/28/leetcode-2322-minimum-score-after-removals-on-a-tree/
码字不易，如果觉得内容有帮助，欢迎留言or点赞！