Minimum Score After Removals on a Tree — LeetCode 2322 Python Solution
HardBit ManipulationTreeDepth-First SearchArray
- Problem
- #2322
- Pattern
- Bit Manipulation
- Reading time
- 6 min
- Source
- leetcode.com
The problem
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.
Example
- 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.
Python solution
Python
class Solution:
def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:
def dfs(i: int, fa: int) -> int:
res = nums[i]
for j in g[i]:
if j != fa:
res ^= dfs(j, i)
return res
def dfs2(i: int, fa: int) -> int:
nonlocal s, s1, ans
res = nums[i]
for j in g[i]:
if j != fa:
s2 = dfs2(j, i)
res ^= s2
mx = max(s ^ s1, s2, s1 ^ s2)
mn = min(s ^ s1, s2, s1 ^ s2)
ans = min(ans, mx - mn)
return res
g = defaultdict(list)
for a, b in edges:
g[a].append(b)
g[b].append(a)
s = reduce(lambda x, y: x ^ y, nums)
n = len(nums)
ans = inf
for i in range(n):
for j in g[i]:
s1 = dfs(i, j)
dfs2(i, j)
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(n^2) |
| Space | O(n), where n is the number of nodes in the tree auxiliary |
Pattern: Bit Manipulation
Use XOR, masks and the low-bit trick to replace whole data structures with an integer. LeetCode 2322. Minimum Score After Removals on a Tree is filed here because LeetCode tags it Bit Manipulation, which is the vocabulary this hub collects.
The bit manipulation guide has the Python template for the pattern and the 194 LeetCode problems that use it.
Related problems
LeetCode 1457Pseudo-Palindromic Paths in a Binary TreeMediumLeetCode 1766Tree of CoprimesHardLeetCode 2049Count Nodes With the Highest ScoreMediumLeetCode 2440Create Components With Same ValueHardLeetCode 2458Height of Binary Tree After Subtree Removal QueriesHardLeetCode 2331Evaluate Boolean Binary TreeEasy
Frequently asked questions
- How hard is LeetCode 2322. Minimum Score After Removals on a Tree?
- LeetCode 2322. Minimum Score After Removals on a Tree is rated Hard on LeetCode.
- What is the time complexity of LeetCode 2322. Minimum Score After Removals on a Tree?
- The Python solution on this page runs in O(n^2).
- What is the space complexity of LeetCode 2322. Minimum Score After Removals on a Tree?
- The Python solution on this page uses O(n), where n is the number of nodes in the tree auxiliary space.
- What topics does LeetCode 2322. Minimum Score After Removals on a Tree cover?
- LeetCode 2322. Minimum Score After Removals on a Tree is tagged Bit Manipulation, Tree, Depth-First Search and Array on LeetCode.