Number of Ways to Assign Edge Weights I - Practice Coding Problems

Number of Ways to Assign Edge Weights I - 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] = [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.

Input & Output

Example 1 — Linear Path Tree

$ Input: n = 4, edges = [[1,2],[2,3],[3,4]]

› Output: 4

💡 Note: Tree is 1→2→3→4. Maximum depth is 3. Path 1→4 has 3 edges. We need odd total weight. Possible assignments: [1,2,2]=5, [2,1,2]=5, [2,2,1]=5, [1,1,1]=3. Total: 4 ways.

Example 2 — Single Edge Tree

$ Input: n = 2, edges = [[1,2]]

› Output: 1

💡 Note: Tree is 1→2. Maximum depth is 1. Path has 1 edge. For odd sum, assign weight 1. Only 1 way: [1]=1.

Example 3 — Branched Tree

$ Input: n = 5, edges = [[1,2],[1,3],[2,4],[2,5]]

› Output: 2

💡 Note: Tree has nodes 4 and 5 at max depth 2. Path 1→2→4 has 2 edges. For odd sum: [1,2]=3 or [2,1]=3. Total: 2 ways.

Constraints

1 ≤ n ≤ 10⁵
edges.length == n - 1
1 ≤ u_i, v_i ≤ n
The input represents a valid tree

Visualization

Tap to expand

Understanding the Visualization

Input Tree

Tree with n nodes, root at node 1

Find Deepest

Use DFS to find maximum depth node

Count Assignments

Calculate 2^(depth-1) weight combinations giving odd sums

Key Takeaway

🎯 Key Insight: For k edges, exactly 2^(k-1) weight assignments produce odd path sums

Asked in

G Google 35 a Amazon 28

The key insight is that for any path with k edges, exactly half of all 2^k weight combinations produce odd sums. This happens when an odd number of edges have weight 1. Best approach uses the mathematical formula 2^(k-1) where k is the depth of the deepest node. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Weight Combinations	O(n + 2^k)	O(n + 2^k)	Generate all possible weight assignments and count those with odd sums
Mathematical Formula - Power of 2	O(n)	O(n)	Use mathematical insight that exactly half of all combinations give odd sums

Brute Force - Try All Weight Combinations — Algorithm Steps

Step 1: Use DFS to find all nodes at maximum depth
Step 2: Find path from root to any deepest node
Step 3: Generate all 2^k weight combinations for k edges
Step 4: Count combinations with odd total weight

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Deepest Node

Use DFS to find maximum depth node

Extract Path

Get path from root to deepest node

Generate Combinations

Try all 2^k weight assignments

Count Odd Sums

Count combinations with odd total weight

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MOD 1000000007
#define MAXN 1005

int graph[MAXN][MAXN];
int degree[MAXN];
int maxDepth = 0;
int deepestNode = 1;
int path[MAXN];
int pathLen = 0;

void dfsDepth(int node, int parent, int depth, int n) {
    if (depth > maxDepth) {
        maxDepth = depth;
        deepestNode = node;
    }
    
    for (int i = 0; i < degree[node]; i++) {
        int neighbor = graph[node][i];
        if (neighbor != parent) {
            dfsDepth(neighbor, node, depth + 1, n);
        }
    }
}

int findPath(int node, int parent, int target, int currentPath[], int currentLen) {
    currentPath[currentLen] = node;
    currentLen++;
    
    if (node == target) {
        for (int i = 0; i < currentLen; i++) {
            path[i] = currentPath[i];
        }
        pathLen = currentLen;
        return 1;
    }
    
    for (int i = 0; i < degree[node]; i++) {
        int neighbor = graph[node][i];
        if (neighbor != parent) {
            if (findPath(neighbor, node, target, currentPath, currentLen)) {
                return 1;
            }
        }
    }
    
    return 0;
}

int solution(int n, int edges[][2], int edgeCount) {
    // Initialize
    memset(degree, 0, sizeof(degree));
    
    // Build adjacency list
    for (int i = 0; i < edgeCount; i++) {
        int u = edges[i][0];
        int v = edges[i][1];
        graph[u][degree[u]++] = v;
        graph[v][degree[v]++] = u;
    }
    
    // Find maximum depth and any node at that depth
    maxDepth = 0;
    deepestNode = 1;
    dfsDepth(1, -1, 0, n);
    
    // Find path from root to deepest node
    int currentPath[MAXN];
    findPath(1, -1, deepestNode, currentPath, 0);
    
    // Number of edges in path
    int numEdges = pathLen - 1;
    
    // Count ways to assign weights (1 or 2) such that sum is odd
    int oddCount = 0;
    int totalCombinations = 1 << numEdges;
    
    for (int mask = 0; mask < totalCombinations; mask++) {
        int totalWeight = 0;
        for (int i = 0; i < numEdges; i++) {
            if (mask & (1 << i)) {
                totalWeight += 1;  // weight 1
            } else {
                totalWeight += 2;  // weight 2
            }
        }
        
        if (totalWeight % 2 == 1) {
            oddCount++;
        }
    }
    
    return oddCount % MOD;
}

int main() {
    int n;
    scanf("%d", &n);
    
    int edges[MAXN][2];
    // Simple parsing - read pairs
    char line[10000];
    fgets(line, sizeof(line), stdin); // consume newline
    fgets(line, sizeof(line), stdin);
    
    int edgeCount = 0;
    char *token = strtok(line, "[],");
    while (token != NULL && edgeCount < n - 1) {
        edges[edgeCount][0] = atoi(token);
        token = strtok(NULL, "[],");
        if (token) {
            edges[edgeCount][1] = atoi(token);
            edgeCount++;
        }
        token = strtok(NULL, "[],");
    }
    
    printf("%d\n", solution(n, edges, edgeCount));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + 2^k)

O(n) for DFS to find deepest node, O(2^k) to generate all combinations where k is path length

✓ Linear Growth

Space Complexity

O(n + 2^k)

O(n) for adjacency list and DFS stack, O(2^k) for storing all weight combinations

⚡ Linearithmic Space

29.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Weight Combinations — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler