3558. Number of Ways to Assign Edge Weights I

Time: O(n + log n)

Space: O(n)

Intuition

Only the path from node 1 to the deepest reachable node matters, because the answer depends on the maximum number of edges that may be assigned weights. If that path has d edges, each edge can be weight 1 or 2, giving 2^d total assignments. Exactly half of those assignments have odd total sum: flipping any one edge toggles the parity, pairing every even-sum assignment with one odd-sum assignment. So the count is 2^(d-1).

Algorithm

1Build an undirected adjacency list from the edge list.
2Run BFS starting at node 1 and mark visited nodes.
3Process BFS level by level; the number of completed levels gives the maximum depth plus one, because level 0 contains the root.
4Let d be the maximum depth in edges. The code computes d - 1 as step - 2 for the exponent.
5Return 2^(d-1) modulo 1,000,000,007 using fast modular exponentiation.
6Time Complexity: O(n + log n), where n is the number of nodes: BFS is linear and modular exponentiation is logarithmic in the depth.
7Space Complexity: O(n), for the adjacency list, queue, and visited array.

Example Walkthrough

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

1.BFS levels from node 1 are: level 0 -> [1], level 1 -> [2,3], level 2 -> [4].
2.The deepest path has d = 2 edges, for example 1 -> 3 -> 4.
3.There are 2^2 = 4 assignments of weights 1/2 on those two edges.
4.Odd sums occur for (1,2) and (2,1), so the answer is 2 = 2^(2-1).

Output: 2

Common Pitfalls

•Depth should be counted in edges, not nodes.
•Use modulo arithmetic for the power calculation.
•The tree is undirected in the input, so add both u->v and v->u to the graph.

3558.cs

// Approach: Build the tree, BFS from node 1 to find the maximum depth in edges, then count
// assignments of weights 1/2 on that deepest path with odd total weight. For d path edges,
// exactly half of the 2^d assignments have odd sum, so the answer is 2^(d-1).
// Time: O(n + log n) Space: O(n)

public class Solution
{
    private const int MOD = 1_000_000_007;

    public int AssignEdgeWeights(int[][] edges)
    {
        int n = edges.Length + 1;
        List<int>[] graph = new List<int>[n + 1];
        for (int i = 0; i <= n; i++)
            graph[i] = new List<int>();

        foreach (var edge in edges)
        {
            int u = edge[0];
            int v = edge[1];
            graph[u].Add(v);
            graph[v].Add(u);
        }

        Queue<int> q = new Queue<int>();
        q.Enqueue(1);
        bool[] seen = new bool[n + 1];
        seen[1] = true;

        int step = 0;
        while (q.Count > 0)
        {
            int sz = q.Count;
            for (int i = 0; i < sz; i++)
            {
                int u = q.Dequeue();
                foreach (int v in graph[u])
                {
                    if (!seen[v])
                    {
                        q.Enqueue(v);
                        seen[v] = true;
                    }
                }
            }
            step++;
        }

        return step > 1 ? ModPow(2, step - 2) : 0;
    }

    private int ModPow(long x, long n)
    {
        if (n == 0)
            return 1;
        if ((n & 1) == 1)
            return (int)(x * ModPow(x % MOD, n - 1) % MOD);
        long half = ModPow(x * x % MOD, n / 2);
        return (int)(half % MOD);
    }
}

Was this solution helpful?