Skip to content

3535. Unit Conversion II πŸ”’

DifficultyMedium

Description

There are n types of units indexed from 0 to n - 1.

You are given a 2D integer array conversions of length n - 1, where conversions[i] = [sourceUniti, targetUniti, conversionFactori]. This indicates that a single unit of type sourceUniti is equivalent to conversionFactori units of type targetUniti.

You are also given a 2D integer array queries of length q, where queries[i] = [unitAi, unitBi].

Return an array answer of length q where answer[i] is the number of units of type unitBi equivalent to 1 unit of type unitAi, and can be represented as p/q where p and q are coprime. Return each answer[i] as pq-1 modulo 109 + 7, where q-1 represents the multiplicative inverse of q modulo 109 + 7.

 

Example 1:

Input: conversions = [[0,1,2],[0,2,6]], queries = [[1,2],[1,0]]

Output: [3,500000004]

Explanation:

  • In the first query, we can convert unit 1 into 3 units of type 2 using the inverse of conversions[0], then conversions[1].
  • In the second query, we can convert unit 1 into 1/2 units of type 0 using the inverse of conversions[0]. We return 500000004 since it is the multiplicative inverse of 2.

Example 2:

Input: conversions = [[0,1,2],[0,2,6],[0,3,8],[2,4,2],[2,5,4],[3,6,3]], queries = [[1,2],[0,4],[6,5],[4,6],[6,1]]

Output: [3,12,1,2,83333334]

Explanation:

  • In the first query, we can convert unit 1 into 3 units of type 2 using the inverse of conversions[0], then conversions[1].
  • In the second query, we can convert unit 0 into 12 units of type 4 using conversions[1], then conversions[3].
  • In the third query, we can convert unit 6 into 1 unit of type 5 using the inverse of conversions[5], the inverse of conversions[2], conversions[1], then conversions[4].
  • In the fourth query, we can convert unit 4 into 2 units of type 6 using the inverse of conversions[3], the inverse of conversions[1], conversions[2], then conversions[5].
  • In the fifth query, we can convert unit 6 into 1/12 units of type 1 using the inverse of conversions[5], the inverse of conversions[2], then conversions[0]. We return 83333334 since it is the multiplicative inverse of 12.

 

Constraints:

  • 2 <= n <= 105
  • conversions.length == n - 1
  • 0 <= sourceUniti, targetUniti < n
  • 1 <= conversionFactori <= 109
  • 1 <= q <= 105
  • queries.length == q
  • 0 <= unitAi, unitBi < n
  • It is guaranteed that unit 0 can be uniquely converted into any other unit through a combination of forward or backward conversions.

Solutions

Solution 1: DFS + Modular Inverse

Thinking

The conversion tree is the same as before, so \(\textit{res}[i]\) β€” how many units of \(i\) equal one unit of \(0\) β€” is already known. Queries ask for a ratio between two units.

The factor from \(\textit{unitA}\) to \(\textit{unitB}\) is \(\textit{res}[B] \cdot \textit{res}[A]^{-1}\). The modulus is prime, so the inverse is \(a^{MOD-2}\).

The conversion relations form a directed tree rooted at \(0\). Starting a DFS from node \(0\), we maintain res[i] as the number of units of type \(i\) that equal \(1\) unit of type \(0\).

For a query \((unitA, unitB)\), the answer is \(\frac{res[unitB]}{res[unitA]}\), which modulo \(10^9 + 7\) equals res[unitB] * res[unitA]^(MOD - 2) % MOD, where MOD - 2 is used to compute the modular inverse via Fermat's little theorem.

The time complexity is \(O(n + q \log MOD)\) and the space complexity is \(O(n)\), where \(n\) is the number of unit types and \(q\) is the number of queries.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def queryConversions(
        self, conversions: List[List[int]], queries: List[List[int]]
    ) -> List[int]:
        def dfs(s: int, mul: int) -> None:
            res[s] = mul
            for t, w in g[s]:
                dfs(t, mul * w % mod)

        mod = 10**9 + 7
        n = len(conversions) + 1
        g = [[] for _ in range(n)]
        for s, t, w in conversions:
            g[s].append((t, w))
        res = [0] * n
        dfs(0, 1)
        ans = []
        for x, y in queries:
            ans.append(res[y] * pow(res[x], mod - 2, mod) % mod)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
    private final int mod = (int) 1e9 + 7;
    private List<int[]>[] g;
    private int[] res;

    public int[] queryConversions(int[][] conversions, int[][] queries) {
        int n = conversions.length + 1;
        g = new List[n];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (var e : conversions) {
            g[e[0]].add(new int[] {e[1], e[2]});
        }

        res = new int[n];
        dfs(0, 1);

        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int x = queries[i][0], y = queries[i][1];
            ans[i] = (int) ((long) res[y] * qpow(res[x], mod - 2) % mod);
        }
        return ans;
    }

    private void dfs(int s, long mul) {
        res[s] = (int) mul;
        for (var e : g[s]) {
            dfs(e[0], mul * e[1] % mod);
        }
    }

    private long qpow(long x, int n) {
        long res = 1;
        while (n > 0) {
            if ((n & 1) == 1) {
                res = res * x % mod;
            }
            x = x * x % mod;
            n >>= 1;
        }
        return res;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    vector<int> queryConversions(vector<vector<int>>& conversions, vector<vector<int>>& queries) {
        const int mod = 1e9 + 7;
        int n = conversions.size() + 1;
        vector<vector<pair<int, int>>> g(n);
        for (auto& e : conversions) {
            g[e[0]].emplace_back(e[1], e[2]);
        }

        vector<int> res(n);

        auto dfs = [&](this auto&& dfs, int s, long long mul) -> void {
            res[s] = mul;
            for (auto [t, w] : g[s]) {
                dfs(t, mul * w % mod);
            }
        };
        dfs(0, 1);

        auto qpow = [&](long long x, int n) {
            long long res = 1;
            while (n) {
                if (n & 1) {
                    res = res * x % mod;
                }
                x = x * x % mod;
                n >>= 1;
            }
            return res;
        };

        vector<int> ans;
        for (auto& q : queries) {
            ans.push_back(res[q[1]] * qpow(res[q[0]], mod - 2) % mod);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
func queryConversions(conversions [][]int, queries [][]int) []int {
    const mod = int(1e9 + 7)
    n := len(conversions) + 1

    g := make([][]struct{ t, w int }, n)
    for _, e := range conversions {
        s, t, w := e[0], e[1], e[2]
        g[s] = append(g[s], struct{ t, w int }{t, w})
    }

    res := make([]int, n)

    var dfs func(int, int)
    dfs = func(s, mul int) {
        res[s] = mul
        for _, e := range g[s] {
            dfs(e.t, mul*e.w%mod)
        }
    }
    dfs(0, 1)

    qpow := func(x, n int) int {
        res := 1
        for n > 0 {
            if n&1 > 0 {
                res = res * x % mod
            }
            x = x * x % mod
            n >>= 1
        }
        return res
    }

    ans := make([]int, len(queries))
    for i, q := range queries {
        ans[i] = res[q[1]] * qpow(res[q[0]], mod-2) % mod
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
function queryConversions(conversions: number[][], queries: number[][]): number[] {
    const mod = BigInt(1e9 + 7);
    const n = conversions.length + 1;

    const g: { t: number; w: number }[][] = Array.from({ length: n }, () => []);
    for (const [s, t, w] of conversions) {
        g[s].push({ t, w });
    }

    const res: number[] = Array(n).fill(0);

    const dfs = (s: number, mul: number): void => {
        res[s] = mul;
        for (const { t, w } of g[s]) {
            dfs(t, Number((BigInt(mul) * BigInt(w)) % mod));
        }
    };
    dfs(0, 1);

    const qpow = (x: number, n: number): number => {
        let res = 1n;
        let a = BigInt(x);
        while (n > 0) {
            if (n & 1) {
                res = (res * a) % mod;
            }
            a = (a * a) % mod;
            n >>= 1;
        }
        return Number(res);
    };

    const ans: number[] = [];
    for (const [x, y] of queries) {
        ans.push(Number((BigInt(res[y]) * BigInt(qpow(res[x], 1e9 + 5))) % mod));
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
impl Solution {
    pub fn query_conversions(conversions: Vec<Vec<i32>>, queries: Vec<Vec<i32>>) -> Vec<i32> {
        const MOD: i64 = 1_000_000_007;
        let n = conversions.len() + 1;

        let mut g = vec![Vec::<(usize, i64)>::new(); n];
        for e in conversions {
            g[e[0] as usize].push((e[1] as usize, e[2] as i64));
        }

        let mut res = vec![0_i64; n];

        fn dfs(s: usize, mul: i64, g: &Vec<Vec<(usize, i64)>>, res: &mut Vec<i64>) {
            res[s] = mul;
            for &(t, w) in &g[s] {
                dfs(t, mul * w % MOD, g, res);
            }
        }

        dfs(0, 1, &g, &mut res);

        fn qpow(mut x: i64, mut n: i32) -> i64 {
            let mut res = 1_i64;
            while n > 0 {
                if n & 1 == 1 {
                    res = res * x % MOD;
                }
                x = x * x % MOD;
                n >>= 1;
            }
            res
        }

        let mut ans = Vec::with_capacity(queries.len());
        for q in queries {
            let x = q[0] as usize;
            let y = q[1] as usize;
            ans.push((res[y] * qpow(res[x], 1_000_000_005) % MOD) as i32);
        }
        ans
    }
}

Solution 2: Explicit Stack + Modular Inverse

Thinking

There are \(n - 1\) conversions and a unique path from \(0\), so the graph is a directed tree rooted at \(0\). With \(n \le 10^5\), recursing from the root and multiplying along the way reaches depth \(n\) on a chain and overflows the call stack. Each unit's factor relative to \(0\) depends only on that path.

An explicit stack of \((unit, accumulated\ factor)\) therefore starts at \((0, 1)\). Popping a frame writes \(\textit{res}[i]\), and each successor is pushed with the current factor multiplied by the edge weight, modulo \(10^9 + 7\).

A query asks for a ratio between two units. The factor from \(\textit{unitA}\) to \(\textit{unitB}\) is \(\textit{res}[B] \cdot \textit{res}[A]^{-1}\). The modulus is prime, so the inverse is \(a^{MOD-2}\).

The conversion relations form a directed tree rooted at \(0\). An explicit stack walks from the root. Each frame is \((unit, accumulated\ factor)\), starting from \((0, 1)\). Popping a frame writes res[i], the number of units of type \(i\) that equal \(1\) unit of type \(0\). Each successor is pushed with the current factor multiplied by the edge weight, modulo \(10^9 + 7\).

For a query \((unitA, unitB)\), the answer is \(\frac{res[unitB]}{res[unitA]}\), which modulo \(10^9 + 7\) equals res[unitB] * res[unitA]^(MOD - 2) % MOD, where MOD - 2 is used to compute the modular inverse via Fermat's little theorem.

The time complexity is \(O(n + q \log MOD)\) and the space complexity is \(O(n)\), where \(n\) is the number of unit types and \(q\) is the number of queries.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def queryConversions(
        self, conversions: List[List[int]], queries: List[List[int]]
    ) -> List[int]:
        mod = 10**9 + 7
        n = len(conversions) + 1
        g = [[] for _ in range(n)]
        for s, t, w in conversions:
            g[s].append((t, w))
        res = [0] * n
        stk = [(0, 1)]
        while stk:
            s, mul = stk.pop()
            res[s] = mul
            for t, w in g[s]:
                stk.append((t, mul * w % mod))
        ans = []
        for x, y in queries:
            ans.append(res[y] * pow(res[x], mod - 2, mod) % mod)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
    private final int mod = (int) 1e9 + 7;

    public int[] queryConversions(int[][] conversions, int[][] queries) {
        int n = conversions.length + 1;
        List<int[]>[] g = new List[n];
        Arrays.setAll(g, k -> new ArrayList<>());
        for (var e : conversions) {
            g[e[0]].add(new int[] {e[1], e[2]});
        }
        int[] res = new int[n];
        Deque<long[]> stk = new ArrayDeque<>();
        stk.push(new long[] {0, 1});
        while (!stk.isEmpty()) {
            long[] cur = stk.pop();
            int s = (int) cur[0];
            long mul = cur[1];
            res[s] = (int) mul;
            for (var e : g[s]) {
                stk.push(new long[] {e[0], mul * e[1] % mod});
            }
        }
        int[] ans = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int x = queries[i][0], y = queries[i][1];
            ans[i] = (int) ((long) res[y] * qpow(res[x], mod - 2) % mod);
        }
        return ans;
    }

    private long qpow(long x, int n) {
        long res = 1;
        while (n > 0) {
            if ((n & 1) == 1) {
                res = res * x % mod;
            }
            x = x * x % mod;
            n >>= 1;
        }
        return res;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public:
    vector<int> queryConversions(vector<vector<int>>& conversions, vector<vector<int>>& queries) {
        const int mod = 1e9 + 7;
        int n = conversions.size() + 1;
        vector<vector<pair<int, int>>> g(n);
        for (auto& e : conversions) {
            g[e[0]].emplace_back(e[1], e[2]);
        }
        vector<int> res(n);
        vector<pair<int, long long>> stk{{0, 1}};
        while (!stk.empty()) {
            auto [s, mul] = stk.back();
            stk.pop_back();
            res[s] = mul;
            for (auto [t, w] : g[s]) {
                stk.push_back({t, mul * w % mod});
            }
        }
        auto qpow = [&](long long x, int n) {
            long long res = 1;
            while (n) {
                if (n & 1) {
                    res = res * x % mod;
                }
                x = x * x % mod;
                n >>= 1;
            }
            return res;
        };
        vector<int> ans;
        for (auto& q : queries) {
            ans.push_back(res[q[1]] * qpow(res[q[0]], mod - 2) % mod);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
func queryConversions(conversions [][]int, queries [][]int) []int {
    const mod = int(1e9 + 7)
    n := len(conversions) + 1

    g := make([][]struct{ t, w int }, n)
    for _, e := range conversions {
        s, t, w := e[0], e[1], e[2]
        g[s] = append(g[s], struct{ t, w int }{t, w})
    }

    res := make([]int, n)
    stk := [][2]int{{0, 1}}
    for len(stk) > 0 {
        cur := stk[len(stk)-1]
        stk = stk[:len(stk)-1]
        s, mul := cur[0], cur[1]
        res[s] = mul
        for _, e := range g[s] {
            stk = append(stk, [2]int{e.t, mul * e.w % mod})
        }
    }

    qpow := func(x, n int) int {
        res := 1
        for n > 0 {
            if n&1 > 0 {
                res = res * x % mod
            }
            x = x * x % mod
            n >>= 1
        }
        return res
    }

    ans := make([]int, len(queries))
    for i, q := range queries {
        ans[i] = res[q[1]] * qpow(res[q[0]], mod-2) % mod
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
function queryConversions(conversions: number[][], queries: number[][]): number[] {
    const mod = BigInt(1e9 + 7);
    const n = conversions.length + 1;

    const g: { t: number; w: number }[][] = Array.from({ length: n }, () => []);
    for (const [s, t, w] of conversions) {
        g[s].push({ t, w });
    }

    const res: number[] = Array(n).fill(0);
    const stk: [number, number][] = [[0, 1]];
    while (stk.length) {
        const [s, mul] = stk.pop()!;
        res[s] = mul;
        for (const { t, w } of g[s]) {
            stk.push([t, Number((BigInt(mul) * BigInt(w)) % mod)]);
        }
    }

    const qpow = (x: number, n: number): number => {
        let res = 1n;
        let a = BigInt(x);
        while (n > 0) {
            if (n & 1) {
                res = (res * a) % mod;
            }
            a = (a * a) % mod;
            n >>= 1;
        }
        return Number(res);
    };

    const ans: number[] = [];
    for (const [x, y] of queries) {
        ans.push(Number((BigInt(res[y]) * BigInt(qpow(res[x], 1e9 + 5))) % mod));
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
impl Solution {
    pub fn query_conversions(conversions: Vec<Vec<i32>>, queries: Vec<Vec<i32>>) -> Vec<i32> {
        const MOD: i64 = 1_000_000_007;
        let n = conversions.len() + 1;

        let mut g = vec![Vec::<(usize, i64)>::new(); n];
        for e in conversions {
            g[e[0] as usize].push((e[1] as usize, e[2] as i64));
        }

        let mut res = vec![0_i64; n];
        let mut stk = vec![(0_usize, 1_i64)];
        while let Some((s, mul)) = stk.pop() {
            res[s] = mul;
            for &(t, w) in &g[s] {
                stk.push((t, mul * w % MOD));
            }
        }

        fn qpow(mut x: i64, mut n: i32) -> i64 {
            let mut res = 1_i64;
            while n > 0 {
                if n & 1 == 1 {
                    res = res * x % MOD;
                }
                x = x * x % MOD;
                n >>= 1;
            }
            res
        }

        let mut ans = Vec::with_capacity(queries.len());
        for q in queries {
            let x = q[0] as usize;
            let y = q[1] as usize;
            ans.push((res[y] * qpow(res[x], 1_000_000_005) % MOD) as i32);
        }
        ans
    }
}

Comments