Number of Ways to Assign Edge Weights I - Solution & Explanation

Problem Overview: You are given a tree where edge weights are not fixed. The task is to count how many valid ways you can assign weights to the edges while satisfying constraints on distances along tree paths. Because the structure is a tree, every pair of nodes has exactly one simple path, which allows the constraints to be analyzed using a single traversal.

Approach 1: Brute Force Enumeration (Exponential Time)

The most direct idea is to try every possible weight assignment for every edge and verify whether the resulting tree satisfies the required distance conditions. If each edge can take two possible weights, the total number of assignments is 2^(n-1) for a tree with n nodes. For each assignment, compute path distances and validate the constraints. This approach runs in O(2^n * n) time with O(n) space. It only works for very small trees and mainly helps build intuition about which edges actually influence the constraints.

Approach 2: Tree DFS + Combinatorics (O(n))

The key observation is that constraints on distances only affect edges that lie on specific paths in the tree. Because a tree has a unique path between any two nodes, you can analyze the structure using a single Depth-First Search. During DFS, track how many constrained nodes appear in each subtree. When a subtree contributes to a constrained path, the connecting edge becomes restricted; otherwise it remains free to choose from the allowed weight options.

Each unrestricted edge multiplies the number of valid assignments. If an edge has two valid weight choices, it contributes a factor of 2 to the total count. By counting how many edges remain unrestricted during the DFS traversal, the final result becomes a simple power calculation such as 2^k where k is the number of flexible edges. The traversal processes every node and edge once, giving O(n) time complexity and O(n) space for recursion and adjacency storage.

This method works because trees eliminate cycles, so each edge’s contribution can be determined independently once the subtree structure is known. DFS naturally exposes parent–child relationships and subtree counts, which makes it ideal for these kinds of constraint propagation problems in tree structures combined with mathematical counting.

Recommended for interviews: The DFS + combinatorics approach is the expected solution. Interviewers typically want to see that you recognize the unique-path property of trees, propagate constraints with a single traversal, and convert the remaining freedom into a mathematical counting formula. Mentioning the brute-force enumeration first shows you understand the search space, but deriving the O(n) DFS counting solution demonstrates stronger algorithmic reasoning.