Question

2322. Minimum Score After Removals on a Tree

中文文档

Description

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 = 6, 1 ^ 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.

Solutions

Solution 1

class Solution:
  def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:
    def dfs(i, fa, x):
      res = nums[i]
      for j in g[i]:
        if j != fa and j != x:
          res ^= dfs(j, i, x)
      return res

    def dfs2(i, fa, x):
      nonlocal s, s1, ans
      res = nums[i]
      for j in g[i]:
        if j != fa and j != x:
          a = dfs2(j, i, x)
          res ^= a
          b = s1 ^ a
          c = s ^ s1
          t = max(a, b, c) - min(a, b, c)
          ans = min(ans, t)
      return res

    g = defaultdict(list)
    for a, b in edges:
      g[a].append(b)
      g[b].append(a)

    s = 0
    for v in nums:
      s ^= v
    n = len(nums)
    ans = inf
    for i in range(n):
      for j in g[i]:
        s1 = dfs(i, -1, j)
        dfs2(i, -1, j)
    return ans

class Solution {
  private int s;
  private int s1;
  private int n;
  private int ans = Integer.MAX_VALUE;
  private int[] nums;
  private List<Integer>[] g;

  public int minimumScore(int[] nums, int[][] edges) {
    n = nums.length;
    g = new List[n];
    this.nums = nums;
    Arrays.setAll(g, k -> new ArrayList<>());
    for (int[] e : edges) {
      int a = e[0], b = e[1];
      g[a].add(b);
      g[b].add(a);
    }
    for (int v : nums) {
      s ^= v;
    }
    for (int i = 0; i < n; ++i) {
      for (int j : g[i]) {
        s1 = dfs(i, -1, j);
        dfs2(i, -1, j);
      }
    }
    return ans;
  }

  private int dfs(int i, int fa, int x) {
    int res = nums[i];
    for (int j : g[i]) {
      if (j != fa && j != x) {
        res ^= dfs(j, i, x);
      }
    }
    return res;
  }

  private int dfs2(int i, int fa, int x) {
    int res = nums[i];
    for (int j : g[i]) {
      if (j != fa && j != x) {
        int a = dfs2(j, i, x);
        res ^= a;
        int b = s1 ^ a;
        int c = s ^ s1;
        int t = Math.max(Math.max(a, b), c) - Math.min(Math.min(a, b), c);
        ans = Math.min(ans, t);
      }
    }
    return res;
  }
}

class Solution {
public:
  vector<int> nums;
  int s;
  int s1;
  int n;
  int ans = INT_MAX;
  vector<vector<int>> g;

  int minimumScore(vector<int>& nums, vector<vector<int>>& edges) {
    n = nums.size();
    g.resize(n, vector<int>());
    for (auto& e : edges) {
      int a = e[0], b = e[1];
      g[a].push_back(b);
      g[b].push_back(a);
    }
    for (int& v : nums) s ^= v;
    this->nums = nums;
    for (int i = 0; i < n; ++i) {
      for (int j : g[i]) {
        s1 = dfs(i, -1, j);
        dfs2(i, -1, j);
      }
    }
    return ans;
  }

  int dfs(int i, int fa, int x) {
    int res = nums[i];
    for (int j : g[i])
      if (j != fa && j != x) res ^= dfs(j, i, x);
    return res;
  }

  int dfs2(int i, int fa, int x) {
    int res = nums[i];
    for (int j : g[i])
      if (j != fa && j != x) {
        int a = dfs2(j, i, x);
        res ^= a;
        int b = s1 ^ a;
        int c = s ^ s1;
        int t = max(max(a, b), c) - min(min(a, b), c);
        ans = min(ans, t);
      }
    return res;
  }
};

func minimumScore(nums []int, edges [][]int) int {
  n := len(nums)
  g := make([][]int, n)
  for _, e := range edges {
    a, b := e[0], e[1]
    g[a] = append(g[a], b)
    g[b] = append(g[b], a)
  }
  s := 0
  for _, v := range nums {
    s ^= v
  }
  s1 := 0
  ans := math.MaxInt32
  var dfs func(int, int, int) int
  var dfs2 func(int, int, int) int
  dfs = func(i, fa, x int) int {
    res := nums[i]
    for _, j := range g[i] {
      if j != fa && j != x {
        res ^= dfs(j, i, x)
      }
    }
    return res
  }
  dfs2 = func(i, fa, x int) int {
    res := nums[i]
    for _, j := range g[i] {
      if j != fa && j != x {
        a := dfs2(j, i, x)
        res ^= a
        b := s1 ^ a
        c := s ^ s1
        t := max(max(a, b), c) - min(min(a, b), c)
        ans = min(ans, t)
      }
    }
    return res
  }
  for i := 0; i < n; i++ {
    for _, j := range g[i] {
      s1 = dfs(i, -1, j)
      dfs2(i, -1, j)
    }
  }
  return ans
}