Skip to content

Practice Number of Ways to Assign Edge Weights I

Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.

Medium#3558
LeetCode Problem

Number of Ways to Assign Edge Weights I

Problem Statement

An undirected tree has nodes 1 through n and is rooted at node 1. Select any one node at maximum depth. On its path from the root, assign each edge a weight of either 1 or 2. Count assignments whose path-weight sum is odd, modulo 1,000,000,007. Edges outside the selected path do not contribute choices; do not add answers across different deepest nodes. Approach: Find maximum depth d, measured in edges. Choosing the weights of the first d - 1 edges fixes which weight the last edge must take to make the sum odd. The answer is 2^(d - 1) modulo 1,000,000,007. An iterative tree traversal avoids call-stack limits on a long chain.

Source: Number of Ways to Assign Edge Weights I on LeetCode. Use the original task for its coding environment and submissions.

Examples

# Example 1

Input
edges = [[1,2],[2,3],[3,4]]
Output
4
Explanation

The deepest path has three edges. Weights (1,1,1), (1,2,2), (2,1,2), and (2,2,1) have odd totals.

Constraints

2 <= n <= 10^5
edges.length == n - 1
edges[i] == [u_i, v_i]
1 <= u_i, v_i <= n
edges represents a valid tree.

How to solve Number of Ways to Assign Edge Weights I

Original notes for interview preparation, written for this problem. Reviewed .

Key insight

On a path with d edges, choose the first d - 1 weights freely; the parity of their sum forces exactly one of the two values for the last edge. The count is 2^(d - 1), and the only real work is finding the maximum depth from node 1.

Why brute force is not enough

Enumerating all 2^d weight assignments along the deepest path is exponential in d, which can be n - 1 = 10^5 - 1 on a chain.

Approach

  1. Build adjacency lists for the undirected tree on nodes 1 through n.
  2. Run a breadth-first search from node 1 recording depth in edges; each node is first reached at its true distance, so the largest depth is d.
  3. Weights 1 and 2 have opposite parity, so for any fixed choice of the first d - 1 edges exactly one value for the last edge makes the total odd, giving 2^(d - 1) assignments.
  4. Compute 2^(d - 1) modulo 1,000,000,007 by repeated squaring or d - 1 doublings with reduction.
  5. Return it; since n is at least 2, d is at least 1 and no zero-edge case arises.

Walkthrough of Example 1

edges = [[1,2],[2,3],[3,4]] → 4

  1. edges are [[1,2],[2,3],[3,4]], a chain rooted at node 1.
  2. Breadth-first search gives depths 0, 1, 2, 3 for nodes 1 through 4, so d = 3 and node 4 is the deepest node.
  3. The first two edges have 2 times 2 = 4 weightings, each forcing the third: (1,1) needs 1, (1,2) needs 2, (2,1) needs 2, (2,2) needs 1.
  4. 2^(3 - 1) = 4, the expected output.

Time and space

Time O(n) · Space O(n). n is the node count; the tree has n - 1 edges so the traversal is linear, the power takes O(log n), and adjacency lists plus depths are linear.

Interview pitfalls

  • Measuring depth in nodes rather than edges, which doubles the answer.
  • Summing over all deepest nodes; one is chosen and all give the same value.
  • Recursive search on a 10^5 node chain overflowing the stack.
  • Computing the power without the modulus; d - 1 can be about 10^5.
  • Sizing arrays by n for 1-indexed nodes.

Follow-up questions interviewers ask

  • How would you count odd sums when weights range from 1 to w?
  • What if the count were summed over every root-to-leaf path?
  • How does this extend to arbitrary node pairs, and what structure answers many such queries fast?

Further reading on the technique: Breadth-first search

Related LeetCode Problems

Practice more problems similar to Number of Ways to Assign Edge Weights I.

Review your practice with PhantomCodeAI

After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.