Is Number of Ways to Assign Edge Weights I easy or hard?

The problem is typically classified as Medium difficulty. The tree traversal itself is straightforward, but the challenge is recognizing how path constraints restrict certain edges while leaving others independent. Once that observation is made, the counting step becomes simple.

Number of Ways to Assign Edge Weights I Python/Java solution

The implementation builds an adjacency list for the tree and runs a recursive or iterative DFS. While traversing, it tracks subtree constraints and counts edges that remain free to choose weights. The final answer is computed using modular exponentiation such as pow(2, k). The same logic works in Python, Java, C++, and Go.

How to solve Number of Ways to Assign Edge Weights I in O(n)?

Build the adjacency list of the tree and run a DFS from any root. During traversal, track how constraints propagate through subtrees and determine whether an edge is forced or still flexible. Count the number of edges that remain unrestricted and compute the number of assignments using a power function like 2^k. Because each edge is processed once, the algorithm runs in linear time.

What is the best approach for Number of Ways to Assign Edge Weights I?

The best approach uses a Depth-First Search (DFS) on the tree combined with combinatorial counting. DFS identifies which edges are constrained by path requirements and which edges remain flexible. Each flexible edge contributes independent choices, so the final answer becomes a power calculation such as 2^k. This produces an O(n) time solution.

Is Number of Ways to Assign Edge Weights I asked at Google/Amazon/Meta?

Tree counting problems that combine DFS with combinatorics are common in interviews at companies like Google, Amazon, and Meta. Variants often ask you to analyze constraints along paths in a tree and count valid configurations. Recognizing the unique-path property of trees is the main skill tested.

What data structure is used in Number of Ways to Assign Edge Weights I?

The main data structure is an adjacency list representing the tree. A DFS traversal explores the graph while maintaining subtree information. The algorithm also relies on simple mathematical counting to compute the total number of valid assignments.

What is the time complexity of Number of Ways to Assign Edge Weights I?

The optimal solution runs in O(n) time where n is the number of nodes in the tree. A single DFS traversal processes every node and edge once, while the final answer is computed using a simple exponentiation step. Space complexity is O(n) due to the adjacency list and recursion stack.

Description Hints 4 Solution Video 30:31

3558. Number of Ways to Assign Edge Weights I

Medium63.7% acceptance2 companies

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] = [u_i, v_i] indicates that there is an edge between nodes u_i and v_i.

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 10⁹ + 7.

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

Example 1:

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:

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 <= 10⁵
edges.length == n - 1
edges[i] == [u_i, v_i]
1 <= u_i, v_i <= n
edges represents a valid tree.

Asked at 2 companies

Amazon Meta

Topics

Hints open one at a time

Hint 1

Depth‑First Search (DFS) to compute the depth of each node from the root.

Hint 2

Find the maximum depth, max_depth.

Hint 3

The number of 2s doesn’t affect parity; we only need an odd number of 1s along the path.

Hint 4

The number of ways to choose an odd count of 1s among max_depth edges is 2^(max_depth-1).

30:31

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def assignEdgeWeights(self, edges: List[List[int]]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[[1,2]]

Input

[[1,2],[1,3],[3,4],[3,5]]

Your code is saved on this device.Solution