Skip to content

4100. Minimum Cost Path With Even XOR Parity

DifficultyHard

Description

You are given a tree with n nodes numbered from 0 to n - 1, represented by a 2D integer array edges. Each edges[i] = [ui, vi, ci] represents an edge between nodes ui and vi with cost ci.

You are also given an integer array values of length n, where values[i] is the value of node i.

A path between two distinct nodes is Balanced-XOR if the bitwise XOR of the values of all nodes on the path, including both endpoints, has an even number of set bits.

The cost of a path is the sum of its edge costs.

Return the minimum cost of a Balanced-XOR path. If no such path exists, return -1.

The number 0 has zero set bits.

 

Example 1:

Input: edges = [[0,1,4],[0,2,6],[0,3,3],[3,4,5]], values = [3,1,7,1,3]

Output: 7

Explanation:

Balanced-XOR Path XOR Value Total Cost
1 - 0 - 2 1 XOR 3 XOR 7 = 5 4 + 6 = 10
1 - 0 - 3 1 XOR 3 XOR 1 = 3 4 + 3 = 7
1 - 0 - 3 - 4 1 XOR 3 XOR 1 XOR 3 = 0 4 + 3 + 5 = 12
2 - 0 - 3 7 XOR 3 XOR 1 = 5 6 + 3 = 9
2 - 0 - 3 - 4 7 XOR 3 XOR 1 XOR 3 = 6 6 + 3 + 5 = 14

The minimum cost is 7, achieved by the path 1 - 0 - 3. Thus, the answer is 7.

Example 2:

Input: edges = [[0,1,5],[1,2,10]], values = [1,7,3]

Output: 5

Explanation:

Balanced-XOR Path XOR Value Total Cost
0 - 1 1 XOR 7 = 6 5
0 - 1 - 2 1 XOR 7 XOR 3 = 5 5 + 10 = 15

The minimum cost is 5, achieved by the path 0 - 1. Thus, the answer is 5.

Example 3:

Input: edges = [[0,1,5],[0,2,7],[0,3,9]], values = [1,3,5,9]

Output: -1

Explanation:

  • Every path between two distinct nodes has an XOR value with an odd number of set bits.
  • Therefore, no Balanced-XOR path exists, so the answer is -1.

 

Constraints:

  • 2 <= n <= 105
  • edges.length == n - 1
  • edges[i] = [ui, vi, ci​​​​​​​]
    • 0 <= ui, vi <= n - 1
    • 1 <= ci <= 109
  • values.length == n
  • 1 <= values[i] <= 109
  • edges represents a valid tree.

Solutions

Solution 1

1


1


1


1

Comments