Daily LeetCode - by Vítor Belim

Description

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.

You are given a 2D integer array queries. For each queries[i] = [u_i, v_i], determine the number of ways to assign weights to edges in the path such that the cost of the path between u_i and v_i is odd.

Return an array answer, where answer[i] is the number of valid assignments for queries[i].

Since the answer may be large, apply modulo 10⁹ + 7 to each answer[i].

Note: For each query, disregard all edges not in the path between node u_i and v_i.

Example 1:

Input: edges = [[1,2]], queries = [[1,1],[1,2]]

Output: [0,1]

Explanation:

Query [1,1]: The path from Node 1 to itself consists of no edges, so the cost is 0. Thus, the number of valid assignments is 0.
Query [1,2]: 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]], queries = [[1,4],[3,4],[2,5]]

Output: [2,1,4]

Explanation:

Query [1,4]: 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.
Query [3,4]: The path from Node 3 to Node 4 consists of one edge (3 → 4). Assigning weight 1 makes the cost odd, while 2 makes it even. Thus, the number of valid assignments is 1.
Query [2,5]: The path from Node 2 to Node 5 consists of three edges (2 → 1, 1 → 3, and 3 → 5). Assigning (1,2,2), (2,1,2), (2,2,1), or (1,1,1) makes the cost odd. Thus, the number of valid assignments is 4.

Constraints:

2 <= n <= 10⁵
edges.length == n - 1
edges[i] == [u_i, v_i]
1 <= queries.length <= 10⁵
queries[i] == [u_i, v_i]
1 <= u_i, v_i <= n
edges represents a valid tree.

Solutions

This code is used to calculate mathematical values based on the distances between pairs of connected points (nodes) in a tree-like network. It defines an LCA (Lowest Common Ancestor) helper class that maps out the network, determines how deep each node is, and uses an efficient shortcutting technique to quickly find the shortest path distance between any two points. The main function, assignEdgeWeights, uses this map to process a list of queries; for each query, it measures the distance (the number of steps) between two specified points and uses a precalculated list of powers of two to return a result equal to 2^{distance - 1} (kept within a standard large mathematical limit, modulo 1,000,000,007).

Language: javascript(2026-06-12 08:13)DONE

CPU Performance75.00%

Memory Performance37.50%

class LCA {
    constructor(edges, root = 1) {
        this.n = edges.length + 1;
        this.m = Math.floor(Math.log(this.n) / Math.log(2)) + 1;
        this.d = new Array(this.n + 1).fill(0);
        this.e = new Array(this.n + 1);
        this.f = new Array(this.n + 1);

        for (let i = 0; i <= this.n; i++) {
            this.e[i] = [];
            this.f[i] = new Array(this.m).fill(0);
        }

        for (let edge of edges) {
            const u = edge[0];
            const v = edge[1];
            this.e[u].push(v);
            this.e[v].push(u);
        }

        this.dfs(root, 0);

        for (let i = 1; i < this.m; i++) {
            for (let x = 1; x <= this.n; x++) {
                this.f[x][i] = this.f[this.f[x][i - 1]][i - 1];
            }
        }
    }

    dfs(x, fa) {
        this.f[x][0] = fa;
        for (let y of this.e[x]) {
            if (y === fa) {
                continue;
            }
            this.d[y] = this.d[x] + 1;
            this.dfs(y, x);
        }
    }

    lca(x, y) {
        if (this.d[x] > this.d[y]) {
            [x, y] = [y, x];
        }

        for (let i = this.m - 1; i >= 0; i--) {
            if (this.d[x] <= this.d[this.f[y][i]]) {
                y = this.f[y][i];
            }
        }

        if (x === y) {
            return x;
        }

        for (let i = this.m - 1; i >= 0; i--) {
            if (this.f[y][i] !== this.f[x][i]) {
                x = this.f[x][i];
                y = this.f[y][i];
            }
        }

        return this.f[x][0];
    }

    dis(x, y) {
        return this.d[x] + this.d[y] - this.d[this.lca(x, y)] * 2;
    }
}

const MOD = 1000000007;
const N = 100010;
const p2 = new Array(N);

(function init() {
    p2[0] = 1;
    for (let i = 1; i < N; i++) {
        p2[i] = (p2[i - 1] * 2) % MOD;
    }
})();

function assignEdgeWeights(edges, queries) {
    const lca = new LCA(edges, 1);
    const m = queries.length;
    const res = new Array(m).fill(0);

    for (let i = 0; i < m; i++) {
        const x = queries[i][0];
        const y = queries[i][1];
        if (x !== y) {
            res[i] = p2[lca.dis(x, y) - 1];
        }
    }

    return res;
}

Description

Solutions

AI Explanation