Package g2301_2400.s2322_minimum_score_after_removals_on_a_tree

Class Solution

java.lang.Object

g2301_2400.s2322_minimum_score_after_removals_on_a_tree.Solution

public class Solution
extends Object

2322 - Minimum Score After Removals on a Tree.<p>Hard</p> <p>There is an undirected connected tree with <code>n</code> nodes labeled from <code>0</code> to <code>n - 1</code> and <code>n - 1</code> edges.</p> <p>You are given a <strong>0-indexed</strong> integer array <code>nums</code> of length <code>n</code> where <code>nums[i]</code> represents the value of the <code>i^th</code> node. You are also given a 2D integer array <code>edges</code> of length <code>n - 1</code> where <code>edges[i] = [a_i, b_i]</code> indicates that there is an edge between nodes <code>a_i</code> and <code>b_i</code> in the tree.</p> <p>Remove two <strong>distinct</strong> edges of the tree to form three connected components. For a pair of removed edges, the following steps are defined:</p> <ol> <li>Get the XOR of all the values of the nodes for <strong>each</strong> of the three components respectively.</li> <li>The <strong>difference</strong> between the <strong>largest</strong> XOR value and the <strong>smallest</strong> XOR value is the <strong>score</strong> of the pair.</li> </ol> <ul> <li>For example, say the three components have the node values: <code>[4,5,7]</code>, <code>[1,9]</code>, and <code>[3,3,3]</code>. The three XOR values are <code>4 ^ 5 ^ 7 = <ins> <strong>6</strong> </ins></code>, <code>1 ^ 9 = <ins> <strong>8</strong> </ins></code>, and <code>3 ^ 3 ^ 3 = <ins> <strong>3</strong> </ins></code>. The largest XOR value is <code>8</code> and the smallest XOR value is <code>3</code>. The score is then <code>8 - 3 = 5</code>.</li> </ul> <p>Return <em>the <strong>minimum</strong> score of any possible pair of edge removals on the given tree</em>.</p> <p><strong>Example 1:</strong></p> <p><img src="https://assets.leetcode.com/uploads/2022/05/03/ex1drawio.png" alt="" /></p> <p><strong>Input:</strong> nums = [1,5,5,4,11], edges = [[0,1],[1,2],[1,3],[3,4]]</p> <p><strong>Output:</strong> 9</p> <p><strong>Explanation:</strong> The diagram above shows a way to make a pair of removals.</p> <ul> <li> <p>The 1^st component has nodes [1,3,4] with values [5,4,11]. Its XOR value is 5 ^ 4 ^ 11 = 10.</p> </li> <li> <p>The 2^nd component has node [0] with value [1]. Its XOR value is 1 = 1.</p> </li> <li> <p>The 3^rd component has node [2] with value [5]. Its XOR value is 5 = 5.</p> </li> </ul> <p>The score is the difference between the largest and smallest XOR value which is 10 - 1 = 9.</p> <p>It can be shown that no other pair of removals will obtain a smaller score than 9.</p> <p><strong>Example 2:</strong></p> <p><img src="https://assets.leetcode.com/uploads/2022/05/03/ex2drawio.png" alt="" /></p> <p><strong>Input:</strong> nums = [5,5,2,4,4,2], edges = [[0,1],[1,2],[5,2],[4,3],[1,3]]</p> <p><strong>Output:</strong> 0</p> <p><strong>Explanation:</strong> The diagram above shows a way to make a pair of removals.</p> <ul> <li> <p>The 1^st component has nodes [3,4] with values [4,4]. Its XOR value is 4 ^ 4 = 0.</p> </li> <li> <p>The 2^nd component has nodes [1,0] with values [5,5]. Its XOR value is 5 ^ 5 = 0.</p> </li> <li> <p>The 3^rd component has nodes [2,5] with values [2,2]. Its XOR value is 2 ^ 2 = 0.</p> </li> </ul> <p>The score is the difference between the largest and smallest XOR value which is 0 - 0 = 0.</p> <p>We cannot obtain a smaller score than 0.</p> <p><strong>Constraints:</strong></p> <ul> <li><code>n == nums.length</code></li> <li><code>3 <= n <= 1000</code></li> <li><code>1 <= nums[i] <= 10⁸</code></li> <li><code>edges.length == n - 1</code></li> <li><code>edges[i].length == 2</code></li> <li><code>0 <= a_i, b_i < n</code></li> <li><code>a_i != b_i</code></li> <li><code>edges</code> represents a valid tree.</li> </ul>

Constructor Summary

Constructors

Constructor	Description
Solution()

Method Summary

Modifier and Type	Method	Description
int	minimumScore(int[] arr, int[][] edges)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

Solution

public Solution()

Method Details

minimumScore

public int minimumScore(int[] arr,
 int[][] edges)