# Number of Ways to Assign Edge Weights I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-ways-to-assign-edge-weights-i)
Canonical: https://scaleengineer.com/dsa/problems/number-of-ways-to-assign-edge-weights-i
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search)
**Data structures:** Tree
---
## Problem
There is an undirected tree with `n` nodes labeled from 1 to `n`, rooted at node 1\. The tree is represented by a 2D integer array `edges` of length `n - 1`, where `edges[i] = [ui, vi]` indicates that there is an edge between nodes `ui` and `vi`.

Initially, all edges have a weight of 0\. You must assign each edge a weight of either **1** or **2**.

The **cost** of a path between any two nodes `u` and `v` is the total weight of all edges in the path connecting them.

Select any one node `x` at the **maximum** depth. Return the number of ways to assign edge weights in the path from node 1 to `x` such that its total cost is **odd**.

Since the answer may be large, return it **modulo** `109 + 7`.

**Note:** Ignore all edges **not** in the path from node 1 to `x`.

**Example 1:**

![](https://assets.glich.co/dsa/number-of-ways-to-assign-edge-weights-i/image0.png)

**Input:** edges = \[\[1,2\]\]

**Output:** 1

**Explanation:**

* The path from Node 1 to Node 2 consists of one edge (`1 → 2`).
* Assigning weight 1 makes the cost odd, while 2 makes it even. Thus, the number of valid assignments is 1.

**Example 2:**

![](https://assets.glich.co/dsa/number-of-ways-to-assign-edge-weights-i/image1.png)

**Input:** edges = \[\[1,2\],\[1,3\],\[3,4\],\[3,5\]\]

**Output:** 2

**Explanation:**

* The maximum depth is 2, with nodes 4 and 5 at the same depth. Either node can be selected for processing.
* For example, the path from Node 1 to Node 4 consists of two edges (`1 → 3` and `3 → 4`).
* Assigning weights (1,2) or (2,1) results in an odd cost. Thus, the number of valid assignments is 2.

**Constraints:**

* `2 <= n <= 105`
* `edges.length == n - 1`
* `edges[i] == [ui, vi]`
* `1 <= ui, vi <= n`
* `edges` represents a valid tree.

# Approaches
## Brute-Force with Recursive Enumeration
This approach first determines the maximum depth of the tree, then explicitly generates every possible weight assignment for a path of that length using recursion. It checks each assignment's total cost and counts how many are odd. This method directly simulates the problem statement but is computationally very expensive.
**Time:** O(n + 2^L). Finding the max depth `L` takes `O(n)` time using BFS. The recursive function has two branches at each of the `L` levels, leading to `O(2^L)` calls. This is exponential and too slow for the given constraints. · **Space:** O(n + L). `O(n)` for the adjacency list and BFS data structures. The recursion depth can go up to `L`, so the call stack uses `O(L)` space. Since `L < n`, this is `O(n)`.
**Pros:** Simple to understand and follows the problem definition directly.
**Cons:** Extremely inefficient due to its exponential time complexity.; Will cause a 'Time Limit Exceeded' error on platforms like LeetCode for the given constraints.
### Explanation
The core idea is to solve the problem by exploring all possibilities. First, we need to know the number of edges in the path, which is simply the maximum depth of the tree, let's call it `L`. We can find `L` using a standard graph traversal like BFS starting from the root (node 1). Once `L` is known, we can define a recursive function that tries assigning weight 1 and weight 2 to each of the `L` edges. For each of the `2^L` total combinations, we calculate the sum and check its parity. A counter is incremented for each combination that results in an odd sum.

```java
class Solution {
    private long MOD = 1000000007;

    public int numberOfWays(int[][] edges) {
        int n = edges.length + 1;
        if (n <= 1) return 0;

        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        int maxDepth = findMaxDepth(n, adj);
        if (maxDepth == 0) return 0;

        return (int) countRecursive(0, maxDepth, 0);
    }

    private long countRecursive(int edgeIndex, int L, int currentParity) {
        if (edgeIndex == L) {
            return currentParity; // Returns 1 if odd, 0 if even
        }

        // Case 1: Assign weight 1 (odd)
        long ways1 = countRecursive(edgeIndex + 1, L, 1 - currentParity);

        // Case 2: Assign weight 2 (even)
        long ways2 = countRecursive(edgeIndex + 1, L, currentParity);

        return (ways1 + ways2) % MOD;
    }

    private int findMaxDepth(int n, List<List<Integer>> adj) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{1, 0}); // {node, depth}
        boolean[] visited = new boolean[n + 1];
        visited[1] = true;
        int maxDepth = 0;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int u = current[0];
            int depth = current[1];
            maxDepth = Math.max(maxDepth, depth);

            for (int v : adj.get(u)) {
                if (!visited[v]) {
                    visited[v] = true;
                    queue.offer(new int[]{v, depth + 1});
                }
            }
        }
        return maxDepth;
    }
}
```
### Algorithm
1. **Build Graph:** Construct an adjacency list representation of the tree from the `edges` array.
2. **Find Max Depth (L):** Perform a Breadth-First Search (BFS) or Depth-First Search (DFS) starting from the root (node 1) to find the maximum depth `L` of any node in the tree. The path from the root to such a node will have `L` edges.
3. **Recursive Enumeration:** Create a recursive function, say `countWays(edgeIndex, currentParity)`, where `edgeIndex` is the current edge on the path (from 0 to L-1) and `currentParity` is the parity of the sum so far (0 for even, 1 for odd).
    - The base case is when `edgeIndex == L`. If `currentParity` is 1 (odd), return 1; otherwise, return 0.
    - In the recursive step, for the `edgeIndex`-th edge, explore both possibilities:
        - Assign weight 1 (odd): This flips the parity. Recursively call `countWays(edgeIndex + 1, 1 - currentParity)`.
        - Assign weight 2 (even): This preserves the parity. Recursively call `countWays(edgeIndex + 1, currentParity)`.
    - The total ways is the sum of the results from these two recursive calls (modulo `10^9 + 7`).
4. **Initial Call:** Start the recursion with `countWays(0, 0)` (0 edges processed, sum is 0 which is even).
5. **Return Result:** The final count is the answer.

## Dynamic Programming on Path Length
This approach also starts by finding the maximum depth `L`. Instead of brute-force, it uses dynamic programming to efficiently count the number of ways. We build up the solution for a path of length `i` based on the solutions for a path of length `i-1`, keeping track of the number of ways to form even and odd sums.
**Time:** O(n + L) = O(n). `O(n)` for finding the max depth `L`. The DP calculation involves a loop that runs `L-1` times, taking `O(L)` time. Since `L < n`, the total complexity is dominated by `O(n)`. · **Space:** O(n). `O(n)` for the adjacency list and BFS data structures. The DP calculation itself is optimized to use `O(1)` space.
**Pros:** Efficient enough to pass the given constraints.; Systematically builds the solution from smaller subproblems.
**Cons:** The calculation part is linear in `L`, which is slightly less optimal than the final approach, though both are dominated by the `O(n)` graph traversal.
### Explanation
After finding the maximum path length `L`, we can solve the counting problem using dynamic programming. Let `odd_ways` be the number of ways to get an odd sum and `even_ways` be the number of ways to get an even sum. We can build the solution iteratively.
For a path of length 1, there's 1 way to get an odd sum (weight 1) and 1 way to get an even sum (weight 2).
For a path of length `i`, we can extend the paths of length `i-1`. An odd sum can be formed by taking an even sum and adding 1, or an odd sum and adding 2. Thus, the new number of odd ways is the sum of the old odd and even ways. The same logic applies to forming an new even sum.

```java
class Solution {
    private long MOD = 1000000007;

    public int numberOfWays(int[][] edges) {
        int n = edges.length + 1;
        if (n <= 1) return 0;

        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        int L = findMaxDepth(n, adj);
        if (L == 0) return 0;

        // DP state for path of length 1
        long evenWays = 1; // assign weight 2
        long oddWays = 1;  // assign weight 1

        // Iterate from path length 2 to L
        for (int i = 2; i <= L; i++) {
            long nextEven = (evenWays + oddWays) % MOD;
            long nextOdd = (evenWays + oddWays) % MOD;
            evenWays = nextEven;
            oddWays = nextOdd;
        }

        return (int) oddWays;
    }

    private int findMaxDepth(int n, List<List<Integer>> adj) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{1, 0}); // {node, depth}
        boolean[] visited = new boolean[n + 1];
        visited[1] = true;
        int maxDepth = 0;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int u = current[0];
            int depth = current[1];
            maxDepth = Math.max(maxDepth, depth);

            for (int v : adj.get(u)) {
                if (!visited[v]) {
                    visited[v] = true;
                    queue.offer(new int[]{v, depth + 1});
                }
            }
        }
        return maxDepth;
    }
}
```
### Algorithm
1. **Build Graph & Find Max Depth (L):** As in the previous approach, use BFS to find the maximum depth `L`.
2. **DP State:** Define a DP state based on the number of edges processed. Let `evenWays[i]` be the number of ways to get an even sum using `i` edges, and `oddWays[i]` be the number of ways to get an odd sum.
3. **DP Initialization:** For a single edge (`i=1`):
    - `evenWays[1] = 1` (by assigning weight 2).
    - `oddWays[1] = 1` (by assigning weight 1).
4. **DP Recurrence:** For `i` from 2 to `L`:
    - To get an even sum for `i` edges: (even sum from `i-1` + even weight) OR (odd sum from `i-1` + odd weight). So, `evenWays[i] = evenWays[i-1] + oddWays[i-1]`.
    - To get an odd sum for `i` edges: (even sum from `i-1` + odd weight) OR (odd sum from `i-1` + even weight). So, `oddWays[i] = evenWays[i-1] + oddWays[i-1]`.
5. **Space Optimization:** Notice that the calculation for `i` only depends on `i-1`. We can use two variables instead of arrays to store the counts for the previous step, reducing space to `O(1)` for the DP part.
6. **Result:** The answer is `oddWays[L]` after iterating up to `L`.

## Combinatorial Analysis and Modular Exponentiation
This is the most efficient and elegant approach. It leverages a combinatorial insight to find the answer directly without iteration or recursion on the path length. After finding the max depth `L`, the problem reduces to a single mathematical calculation which can be performed very quickly.
**Time:** O(n + log L) = O(n). `O(n)` for finding the max depth `L` via BFS. The modular exponentiation takes `O(log L)` time. The overall complexity is dominated by the `O(n)` graph traversal. · **Space:** O(n). `O(n)` for the adjacency list and BFS data structures. The modular exponentiation function uses `O(1)` space for the iterative version.
**Pros:** Most efficient method, especially the calculation part.; Code is concise and clean.
**Cons:** Requires recognizing the underlying mathematical pattern or combinatorial identity.
### Explanation
The most direct solution comes from a mathematical observation. A sum of integers is odd if and only if it contains an odd number of odd integers. In our case, the weights are 1 (odd) and 2 (even). Therefore, for the total path cost to be odd, we must assign weight 1 to an odd number of edges on the path.

Let the path length be `L`. The total number of ways to assign weights to `L` edges is `2^L`. For any path of length `i`, the number of ways to get an odd sum is equal to the number of ways to get an even sum, which is `2^(i-1)`. This can be proven by induction or by the DP relations from the previous approach. For a path of length `L`, the number of ways to get an odd sum is `2^(L-1)`.

We first find `L` using BFS, and then compute `2^(L-1)` modulo `10^9 + 7` using modular exponentiation.

```java
class Solution {
    private long MOD = 1000000007;

    public int numberOfWays(int[][] edges) {
        int n = edges.length + 1;
        if (n <= 1) return 0;

        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            adj.add(new ArrayList<>());
        }
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }

        int L = findMaxDepth(n, adj);
        if (L == 0) return 0;

        return (int) power(2, L - 1);
    }

    private long power(long base, long exp) {
        long res = 1;
        base %= MOD;
        while (exp > 0) {
            if (exp % 2 == 1) res = (res * base) % MOD;
            base = (base * base) % MOD;
            exp /= 2;
        }
        return res;
    }

    private int findMaxDepth(int n, List<List<Integer>> adj) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{1, 0}); // {node, depth}
        boolean[] visited = new boolean[n + 1];
        visited[1] = true;
        int maxDepth = 0;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int u = current[0];
            int depth = current[1];
            maxDepth = Math.max(maxDepth, depth);

            for (int v : adj.get(u)) {
                if (!visited[v]) {
                    visited[v] = true;
                    queue.offer(new int[]{v, depth + 1});
                }
            }
        }
        return maxDepth;
    }
}
```
### Algorithm
1. **Build Graph & Find Max Depth (L):** Use BFS to find the maximum depth `L` of the tree, which corresponds to the number of edges in the path.
2. **Combinatorial Insight:** Realize that the total path cost is odd if and only if the number of edges with weight 1 (an odd weight) is odd. The problem is thus equivalent to choosing an odd number of edges out of `L` to assign weight 1.
3. **Mathematical Formula:** The number of ways to choose an odd number of items from a set of `L` is given by the sum `C(L, 1) + C(L, 3) + C(L, 5) + ...`. This sum is a known combinatorial identity that equals `2^(L-1)` for `L > 0`.
4. **Calculation:** The number of ways is `2^(L-1)`. We need to compute this value modulo `10^9 + 7`.
5. **Modular Exponentiation:** Use the efficient 'exponentiation by squaring' algorithm to calculate `pow(2, L-1)` under the given modulus. This computes the result in logarithmic time with respect to the exponent.