Skip to content

Practice Number of Ways to Assign Edge Weights II

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

Hard#3559
LeetCode Problem

Number of Ways to Assign Edge Weights II

Problem Statement

A valid undirected tree connects nodes 1 through n. For each query [u, v], consider only the edges on the unique path between u and v. Give each of those edges weight 1 or 2 and count assignments with an odd total. Return the counts in query order, each modulo 1,000,000,007. Queries are independent; edges outside their paths add no choices. Approach: A path with d > 0 edges has 2^(d - 1) odd-sum assignments. A node queried against itself has zero edges and therefore zero valid assignments. Precompute depths, lowest common ancestors, and powers of two. Then use d = depth[u] + depth[v] - 2 * depth[LCA(u,v)].

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

Examples

# Example 1

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

The three paths have lengths 3, 0, and 2. The zero-edge path has only the even total zero.

Constraints

2 <= n <= 10^5
edges.length == n - 1
edges[i] == [u_i, v_i]
1 <= queries.length <= 10^5
queries[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 II

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

Key insight

The count depends only on the number of edges d on the path: 2^(d - 1) when d is positive and 0 when u equals v. Path length in a tree is depth of u plus depth of v minus twice the depth of their lowest common ancestor, so the problem reduces to fast LCA queries.

Why brute force is not enough

Walking the path per query costs up to n edges, so 10^5 queries on a 10^5 node chain approach 10^10 steps.

Approach

  1. Root the tree at node 1 and run an iterative traversal recording each node's depth and parent.
  2. Build a binary lifting table where level j holds each node's 2^j-th ancestor, filled from level j - 1 by jumping twice; about 17 levels cover 10^5 nodes.
  3. Precompute powers of two modulo 1,000,000,007 up to n.
  4. Per query, lift the deeper node by the depth difference, then lift both from the highest level down whenever their ancestors differ; the invariant is that both stay at equal depth below the LCA until one final step reaches it.
  5. Compute d from the depths and the LCA depth; answer 0 if d is 0, otherwise the stored 2^(d - 1).

Walkthrough of Example 1

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

  1. edges are [[1,2],[2,3],[3,4]], a chain; depths are 0, 1, 2, 3 for nodes 1 through 4.
  2. Query [1,4]: the LCA is node 1 at depth 0, so d = 0 + 3 - 0 = 3 and the answer is 2^2 = 4.
  3. Query [2,2]: the LCA is node 2, so d = 1 + 1 - 2 = 0 and the answer is 0 because the empty sum is even.
  4. Query [2,4]: the LCA is node 2 at depth 1, so d = 1 + 3 - 2 = 2 and the answer is 2^1 = 2.
  5. The results are [4,0,2], the expected output.

Time and space

Time O((n + q) log n) · Space O(n log n). n is the node count and q the query count; the lifting table costs O(n log n) to build and store, and each LCA query is O(log n).

Interview pitfalls

  • Returning 1 or trying 2^(-1) when u equals v; the answer is 0.
  • Lifting both nodes before equalizing depths, which can skip past the common ancestor.
  • Filling the ancestor table in the wrong order so level j reads unfinished entries.
  • Recursive depth-first search on a chain of 10^5 nodes overflowing the stack.
  • Forgetting the modulus or using 32-bit intermediates in the power computation.

Follow-up questions interviewers ask

  • How would an Euler tour plus sparse table give O(1) LCA, and when is that worth it?
  • What if each query also demanded a specific remainder of the sum modulo 3?
  • With weights from 1 to w for larger w, what is the closed form for odd sums?

Further reading on the technique: Lowest common ancestor

Related LeetCode Problems

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

Review your practice with PhantomCodeAI

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