3558. Number of Ways to Assign Edge Weights I

// 演算法 / Algorithm:
// 1) 用 BFS 從根節點 1 算出最大深度 d。
//    BFS from root (node 1) to find the maximum depth d.
// 2) 答案是 2^(d-1) mod 1e9+7（路徑上選奇數條邊為權重 1 的方法數）。
//    Answer is 2^(d-1) mod 1e9+7, the number of ways to pick an odd subset of d edges.

#define MOD 1000000007L  // 取模常數 / the modulus 10^9 + 7

// 快速冪：在 O(log e) 時間算出 base^e mod MOD。
// Fast exponentiation: computes base^e mod MOD in O(log e).
long power(long base, long e) {
    long result = 1;                 // 累積結果，從 1 開始 / running product, starts at 1
    base %= MOD;                     // 先取模，避免 base 過大 / reduce base mod MOD first
    while (e > 0) {                  // 逐個處理指數的二進位位元 / process each bit of the exponent
        if (e & 1)                   // 若當前最低位是 1（e 為奇數）/ if the lowest bit is set
            result = result * base % MOD;  // 把這個 base 的次方乘進結果 / fold this power into result
        base = base * base % MOD;    // base 平方，對應下一個位元 / square base for the next bit
        e >>= 1;                     // 指數右移一位 / shift exponent right by one bit
    }
    return result;
}

int assignEdgeWeights(int** edges, int edgesSize, int* edgesColSize) {
    int n = edgesSize + 1;           // 樹有 n 個節點，邊數 = n-1 / n nodes, since edges = n-1

    // ---- 建立鄰接表 / Build adjacency list ----
    // adjCount[u] 記錄節點 u 有幾個鄰居 / number of neighbors of node u
    int* adjCount = (int*)calloc(n + 1, sizeof(int));  // calloc 會把記憶體清為 0 / calloc zeroes memory
    for (int i = 0; i < edgesSize; i++) {  // 先數每個節點的鄰居數 / first count neighbors per node
        adjCount[edges[i][0]]++;     // 邊的一端 +1 / one endpoint
        adjCount[edges[i][1]]++;     // 另一端 +1（無向邊雙向）/ the other endpoint (undirected)
    }

    // adj[u] 是一個動態陣列，存節點 u 的所有鄰居 / adj[u] holds u's neighbors
    int** adj = (int**)malloc((n + 1) * sizeof(int*));  // 指標陣列 / array of pointers
    int* idx = (int*)calloc(n + 1, sizeof(int));        // 每個 u 目前已填入幾個鄰居 / fill position per node
    for (int u = 1; u <= n; u++)
        adj[u] = (int*)malloc(adjCount[u] * sizeof(int));  // 為每個節點配置剛好夠用的空間 / exact-size buffer
    for (int i = 0; i < edgesSize; i++) {  // 第二趟：真正填入鄰居 / second pass: fill neighbors
        int u = edges[i][0], v = edges[i][1];
        adj[u][idx[u]++] = v;        // 把 v 加到 u 的清單，idx[u] 後移 / append v to u, advance write index
        adj[v][idx[v]++] = u;        // 把 u 加到 v 的清單 / append u to v
    }

    // ---- BFS 求最大深度 / BFS to find max depth ----
    int* depth = (int*)malloc((n + 1) * sizeof(int));   // 每個節點的深度 / depth of each node
    char* visited = (char*)calloc(n + 1, sizeof(char)); // 標記是否已走訪，避免回頭 / visited flag
    int* queue = (int*)malloc(n * sizeof(int));         // 用陣列當佇列 / array used as a queue
    int head = 0, tail = 0;          // head 指向待取出位置，tail 指向待寫入位置 / read/write cursors

    queue[tail++] = 1;               // 從根節點 1 開始 / start BFS at root node 1
    visited[1] = 1;                  // 標記根已走訪 / mark root visited
    depth[1] = 0;                    // 根的深度為 0 / root depth is 0
    int maxDepth = 0;                // 目前看到的最大深度 / max depth seen so far

    while (head < tail) {            // 佇列還有節點就繼續 / while queue is not empty
        int u = queue[head++];       // 取出隊首節點 / dequeue front node
        if (depth[u] > maxDepth)     // 更新最大深度 / update the maximum depth
            maxDepth = depth[u];
        for (int j = 0; j < adjCount[u]; j++) {  // 走訪 u 的每個鄰居 / iterate neighbors of u
            int w = adj[u][j];
            if (!visited[w]) {       // 沒走訪過才處理（樹不會有環，但仍要防回到父節點）/ skip the parent
                visited[w] = 1;      // 標記已走訪 / mark visited
                depth[w] = depth[u] + 1;  // 子節點深度 = 父深度 + 1 / child depth = parent + 1
                queue[tail++] = w;   // 加入佇列 / enqueue child
            }
        }
    }

    // ---- 釋放記憶體 / Free memory ----
    for (int u = 1; u <= n; u++) free(adj[u]);  // 釋放每個鄰居清單 / free each neighbor list
    free(adj); free(adjCount); free(idx);
    free(depth); free(visited); free(queue);

    // 答案 = 2^(maxDepth - 1) mod 1e9+7 / answer = 2^(maxDepth-1)
    return (int)power(2, maxDepth - 1);
}

// 演算法 / Algorithm:
// 1) 用 BFS 從根節點 1 求最大深度 d。 BFS from root to find max depth d.
// 2) 回傳 2^(d-1) mod 1e9+7。 Return 2^(d-1) mod 1e9+7.

class Solution {
    static const long MOD = 1000000007L;  // 取模常數 / the modulus 10^9 + 7

    // 快速冪 / fast exponentiation: base^e mod MOD in O(log e)
    long power(long base, long e) {
        long result = 1;                   // 累積乘積 / running product
        base %= MOD;
        while (e > 0) {                    // 逐位處理指數 / process exponent bit by bit
            if (e & 1) result = result * base % MOD;  // 此位為 1 就乘入 / fold in when bit set
            base = base * base % MOD;       // base 平方 / square the base
            e >>= 1;                        // 指數右移 / shift exponent
        }
        return result;
    }

public:
    int assignEdgeWeights(vector<vector<int>>& edges) {
        int n = edges.size() + 1;          // 節點數 = 邊數 + 1 / nodes = edges + 1

        // 鄰接表：adj[u] 是 vector，存 u 的所有鄰居。
        // Adjacency list: adj[u] is a vector holding u's neighbors.
        vector<vector<int>> adj(n + 1);    // 索引 0 不用，1..n / index 0 unused
        for (auto& e : edges) {            // range-for：依序取出每條邊 / range-for over edges
            adj[e[0]].push_back(e[1]);     // push_back：往 vector 尾端加元素 / append neighbor
            adj[e[1]].push_back(e[0]);     // 無向邊兩端都要加 / undirected: both directions
        }

        // BFS 求最大深度 / BFS to find max depth
        vector<int> depth(n + 1, 0);       // 每個節點的深度，初始 0 / depths, all 0
        vector<bool> visited(n + 1, false);// 走訪標記 / visited flags
        queue<int> q;                      // STL 佇列，先進先出 / FIFO queue
        q.push(1);                         // 從根節點 1 出發 / start at root
        visited[1] = true;
        int maxDepth = 0;

        while (!q.empty()) {               // 佇列非空就繼續 / until queue drains
            int u = q.front(); q.pop();    // front 取隊首、pop 移除 / read and remove front
            maxDepth = max(maxDepth, depth[u]);  // 更新最大深度 / track the deepest level
            for (int w : adj[u]) {         // 走訪鄰居 / visit each neighbor
                if (!visited[w]) {         // 跳過已走訪（即父節點）/ skip the parent
                    visited[w] = true;
                    depth[w] = depth[u] + 1;  // 子深度 = 父深度 + 1 / child = parent + 1
                    q.push(w);             // 入列 / enqueue
                }
            }
        }

        // 答案 / answer = 2^(maxDepth-1) mod 1e9+7
        return (int)power(2, maxDepth - 1);
    }
};