You are given an undirected tree rooted at node $1$ with $n$ nodes labeled from $1$ to $n$, represented by a $2 ext{D}$ integer array edges of length $n - 1$, where edges[i] = [$u_i$, $v_i$] indicates an edge between node $u_i$ and node $v_i$.

Consider the simple path from root node $1$ to any node that is at the maximum depth from node $1$. Each edge along this path must be assigned an integer weight of either $1$ or $2$.

Return the number of ways to assign weights to the edges on this path such that the total sum of the edge weights along the path is odd.

Constraints:

• $2 \leq n \leq 10^5$

• edges.length $= n - 1$

• edges[i] = [$u_i$, $v_i$]

• $1 \leq u_i, v_i \leq n$

• edges represents a valid tree.

Now, let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Implement your solution in the following coding playground.