3558. Number of Ways to Assign Edge Weights I

class Solution {
    private static final int MOD = 1_000_000_007;

    public int assignEdgeWeights(int[][] edges) {
        int n = edges.length + 1;

        List<Integer>[] graph = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }

        for (int[] e : edges) {
            graph[e[0]].add(e[1]);
            graph[e[1]].add(e[0]);
        }

        // Find maximum depth from root (node 1)
        int maxDepth = 0;
        boolean[] vis = new boolean[n + 1];

        Queue<int[]> q = new LinkedList<>();
        q.offer(new int[]{1, 0});
        vis[1] = true;

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int node = cur[0];
            int depth = cur[1];

            maxDepth = Math.max(maxDepth, depth);

            for (int nxt : graph[node]) {
                if (!vis[nxt]) {
                    vis[nxt] = true;
                    q.offer(new int[]{nxt, depth + 1});
                }
            }
        }

        // Number of odd-sum assignments on a path of length maxDepth
        long ans = 1;
        for (int i = 1; i < maxDepth; i++) {
            ans = (ans * 2) % MOD;
        }

        return (int) ans;
    }
}

from collections import deque

class Solution:
    MOD = 1_000_000_007

    def assignEdgeWeights(self, edges):

        n = len(edges) + 1

        graph = [[] for _ in range(n + 1)]

        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        vis = [False] * (n + 1)

        q = deque([(1, 0)])
        vis[1] = True

        maxDepth = 0

        while q:

            node, depth = q.popleft()

            maxDepth = max(maxDepth, depth)

            for nxt in graph[node]:
                if not vis[nxt]:
                    vis[nxt] = True
                    q.append((nxt, depth + 1))

        return pow(2, maxDepth - 1, self.MOD) if maxDepth > 0 else 1

class Solution {
public:

    static constexpr int MOD = 1000000007;

    int assignEdgeWeights(vector<vector<int>>& edges) {

        int n = edges.size() + 1;

        vector<vector<int>> graph(n + 1);

        for (auto &e : edges) {
            graph[e[0]].push_back(e[1]);
            graph[e[1]].push_back(e[0]);
        }

        queue<pair<int,int>> q;

        vector<int> vis(n + 1, 0);

        q.push({1,0});
        vis[1]=1;

        int maxDepth=0;

        while(!q.empty()){

            auto [node,depth]=q.front();
            q.pop();

            maxDepth=max(maxDepth,depth);

            for(int nxt:graph[node]){

                if(!vis[nxt]){

                    vis[nxt]=1;
                    q.push({nxt,depth+1});
                }
            }
        }

        long long ans=1;

        for(int i=1;i<maxDepth;i++)
            ans=(ans*2)%MOD;

        return ans;
    }
};

var assignEdgeWeights = function(edges) {

    const MOD = 1000000007;

    const n = edges.length + 1;

    const graph = Array.from(
        {length:n+1},
        ()=>[]
    );

    for(const [u,v] of edges){

        graph[u].push(v);
        graph[v].push(u);
    }

    const vis = new Array(n+1).fill(false);

    const q=[[1,0]];

    vis[1]=true;

    let front=0;
    let maxDepth=0;

    while(front<q.length){

        const [node,depth]=q[front++];

        maxDepth=Math.max(maxDepth,depth);

        for(const nxt of graph[node]){

            if(!vis[nxt]){

                vis[nxt]=true;

                q.push([nxt,depth+1]);
            }
        }
    }

    let ans=1n;

    for(let i=1;i<maxDepth;i++){

        ans=(ans*2n)%1000000007n;
    }

    return Number(ans);
};