Practice/Google/Leetcode 2445. Number of Nodes With Value One

Leetcode 2445. Number of Nodes With Value One

CodingMust

Problem

You are given a tree with n nodes numbered from 0 to n-1. Each node has an initial binary value (either 0 or 1). The tree structure is defined by a list of edges where each edge connects two nodes.

Additionally, you are given a list of node indices called flips. When a node is in the flips list, it triggers a flip operation that propagates down the tree: every node in the subtree rooted at that flip node (including the flip node itself) has its value XORed with 1.

Multiple flip operations can affect the same node, and their effects accumulate through XOR. Your task is to determine how many nodes have a final value of 1 after all flip operations have been applied.

Requirements

1. Build the tree structure from the given edges
2. Apply all flip operations by propagating XOR changes down each subtree
3. Count the total number of nodes that have value 1 after all operations
4. Handle cases where multiple flips affect overlapping subtrees

Constraints

• 1 <= n <= 10^5 where n is the number of nodes
• values.length == n
• values[i] is either 0 or 1
• edges.length == n - 1 (valid tree structure)
• 0 <= flips.length <= n
• All values in flips are valid node indices
• The tree is connected and acyclic
• Expected time complexity: O(n)
• Expected space complexity: O(n)

Examples

Example 1:

` Input: values = [0, 1, 0, 1] edges = [[0,1],[0,2],[1,3]] flips = [0, 1] Output: 3 Explanation: Tree structure: 0(0) /
1(1) 2(0) | 3(1)

Flip at node 0: All nodes get XORed with 1 [1, 0, 1, 0] Flip at node 1: Node 1 and its subtree (node 3) get XORed with 1 [1, 1, 1, 1] But we need to track cumulative flips properly via DFS. Final count: 3 nodes with value 1 `

Example 2:

Input: values = [1, 0, 1, 0] edges = [[0,1],[0,2],[2,3]] flips = [] Output: 2 Explanation: No flip operations are applied, so we just count initial 1s. Nodes 0 and 2 have value 1.

Example 3:

Input: values = [0] edges = [] flips = [0] Output: 1 Explanation: Single node tree. Node 0 starts at 0, gets flipped to 1.