2322. Minimum Score After Removals on a Tree


题目

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:

  1. Get the XOR of all the values of the nodes for each of the three components respectively.
  2. 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 are 4 ^ 5 ^ 7 = 61 ^ 9 = 8, and 3 ^ 3 ^ 3 = 3. The largest XOR value is 8 and the smallest XOR value is 3. The score is then 8 - 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.length
  • 3 <= n <= 1000
  • 1 <= nums[i] <= 108
  • edges.length == n - 1
  • edges[i].length == 2
  • 0 <= ai, bi < n
  • ai != bi
  • edges represents 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点赞!


发表回复

您的电子邮箱地址不会被公开。