Tap here to switch tabs
Problem
Submissions

Problem: Minimum Score After Removals on a Tree

Try to solve the Minimum Score After Removals on a Tree problem.

Statement

You are given an undirected tree consisting of n nodes numbered from 00 to n −1- 1, and an integer array nums of length n where nums[i] represents the value assigned to the iith node. You are also given a 22D integer array edges of length n −1- 1, where edges[i] = [a_i, b_i] denotes an undirected edge connecting nodes a_i and b_i.

Two distinct edges are chosen and removed from the tree, dividing it into three separate connected components.

The XOR value of a component is defined as the bitwise XOR sum of the values of all nodes in that component.

The score of a pair of removed edges is the difference between the largest XOR value and the smallest XOR value among the three resulting components.

Return the minimum possible score that can be obtained by removing two distinct edges.

Constraints:

  • n ==== nums.length

  • 3≤3 \leq n ≤1000\leq 1000

  • 1≤1 \leq nums[i] ≤108\leq 10^8

  • edges.length ==== n −1- 1

  • edges[i].length ==2== 2

  • 0≤0 \leq a_i, b_i << n

  • a_i ≠\neq b_i

  • edges forms a valid tree.

⋮
Tap here to switch tabs
Problem
Submissions

Problem: Minimum Score After Removals on a Tree

Try to solve the Minimum Score After Removals on a Tree problem.

Statement

You are given an undirected tree consisting of n nodes numbered from 00 to n −1- 1, and an integer array nums of length n where nums[i] represents the value assigned to the iith node. You are also given a 22D integer array edges of length n −1- 1, where edges[i] = [a_i, b_i] denotes an undirected edge connecting nodes a_i and b_i.

Two distinct edges are chosen and removed from the tree, dividing it into three separate connected components.

The XOR value of a component is defined as the bitwise XOR sum of the values of all nodes in that component.

The score of a pair of removed edges is the difference between the largest XOR value and the smallest XOR value among the three resulting components.

Return the minimum possible score that can be obtained by removing two distinct edges.

Constraints:

  • n ==== nums.length

  • 3≤3 \leq n ≤1000\leq 1000

  • 1≤1 \leq nums[i] ≤108\leq 10^8

  • edges.length ==== n −1- 1

  • edges[i].length ==2== 2

  • 0≤0 \leq a_i, b_i << n

  • a_i ≠\neq b_i

  • edges forms a valid tree.