Problem statement

There are n types of units numbered 0 to n - 1. You are given n - 1 conversions; conversions[i] = [sourceUnit, targetUnit, conversionFactor] means that one unit of type sourceUnit equals conversionFactor units of type targetUnit.

The conversions are arranged so that, starting from unit 0 and following them in their given direction, every other unit can be reached in exactly one way.

Return an array baseUnitConversion of length n where baseUnitConversion[i] is the number of units of type i equal to one unit of type 0. The numbers can be huge, so return each one modulo 10^9 + 7.

Example 1

Input: conversions = [[0,1,2],[1,2,3]]
Output: [1,2,6]
Explanation: One unit of type 0 is 2 units of type 1, and 2 · 3 = 6 units of type 2.

Example 2

Input: conversions = [[0,1,2],[0,2,3],[1,3,4],[1,4,5],[2,5,2],[4,6,3],[5,7,4]]
Output: [1,2,3,8,10,6,30,24]

Example 3

Input: conversions = [[0,1,1000000000],[1,2,1000000000]]
Output: [1,1000000000,49]
Explanation: 10^18 modulo 10^9 + 7 is 49.

Constraints

• 2 <= n <= 10^5
• conversions.length == n - 1
• 0 <= sourceUnit, targetUnit < n
• 1 <= conversionFactor <= 10^9
• unit 0 can be converted into every other unit through exactly one chain of conversions

Hints for Unit Conversion I

1. Hint 1

   Draw each conversion as a directed edge from source to target with the factor as its weight. The guarantee makes this a tree hanging from unit 0.

2. Hint 2

   The answer for a unit is the product of the factors along the path from 0 to it, so it is the parent's answer times the edge's factor.

3. Hint 3

   BFS or DFS from 0, multiplying as you go, and reduce modulo 10^9 + 7 after every multiplication — the product of two residues needs 64-bit arithmetic.

How to solve Unit Conversion I

The conversions form a tree rooted at unit 0, and converting along a path multiplies the factors. One traversal from the root fills in every product.

Approach

1. Build directed adjacency lists source → (target, factor).
2. Set ans[0] = 1 and traverse from 0 (BFS or an explicit stack).
3. For an edge u → v with factor f, set ans[v] = ans[u] · f mod (10^9 + 7).
4. Return ans.

Why it works

One unit of type 0 equals ans[u] units of type u, and each of those equals f units of v, so it equals ans[u] · f units of v. The path from 0 to v is unique, so the value is well defined; taking it modulo the prime at each step is exact because multiplication commutes with the modulus.

Complexity

• Time — O(n)
• Space — O(n)

Pitfalls

• Two factors near 10^9 multiply to about 10^18: use 64-bit integers (or BigInt / a split multiplication in JavaScript, whose doubles lose precision past 2^53).
• Edges are directed: follow them only from source to target.
• Reduce after every multiplication, not just at the end.

Reference solution

Python

from typing import List

def baseUnitConversion(conversions: List[List[int]]) -> List[int]:
    MOD = 10**9 + 7
    n = len(conversions) + 1
    adj = [[] for _ in range(n)]
    for s, t, f in conversions:
        adj[s].append((t, f))
    ans = [0] * n
    ans[0] = 1
    stack = [0]
    while stack:
        u = stack.pop()
        for v, f in adj[u]:
            ans[v] = ans[u] * f % MOD
            stack.append(v)
    return ans

Java

public static int[] baseUnitConversion(int[][] conversions) {
    final long MOD = 1000000007L;
    int n = conversions.length + 1;
    List<List<Integer>> adj = new ArrayList<>();
    for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
    for (int e = 0; e < conversions.length; e++) adj.get(conversions[e][0]).add(e);
    long[] val = new long[n];
    val[0] = 1;
    int[] stack = new int[n];
    int top = 0;
    stack[top++] = 0;
    while (top > 0) {
        int u = stack[--top];
        for (int e : adj.get(u)) {
            int v = conversions[e][1];
            val[v] = val[u] * conversions[e][2] % MOD;
            stack[top++] = v;
        }
    }
    int[] ans = new int[n];
    for (int i = 0; i < n; i++) ans[i] = (int) val[i];
    return ans;
}

C++

vector<int> baseUnitConversion(vector<vector<int>>& conversions) {
    const long long MOD = 1000000007LL;
    int n = conversions.size() + 1;
    vector<vector<int>> adj(n);
    for (int e = 0; e < (int) conversions.size(); e++) adj[conversions[e][0]].push_back(e);
    vector<long long> val(n, 0);
    val[0] = 1;
    vector<int> stack = {0};
    while (!stack.empty()) {
        int u = stack.back();
        stack.pop_back();
        for (int e : adj[u]) {
            int v = conversions[e][1];
            val[v] = val[u] * conversions[e][2] % MOD;
            stack.push_back(v);
        }
    }
    vector<int> ans(n);
    for (int i = 0; i < n; i++) ans[i] = (int) val[i];
    return ans;
}

JavaScript

var baseUnitConversion = function(conversions) {
    var n = conversions.length + 1, adj = [], ans = [];
    for (var i = 0; i < n; i++) { adj.push([]); ans.push(0); }
    for (var e = 0; e < conversions.length; e++) adj[conversions[e][0]].push(e);
    ans[0] = 1;
    var stack = [0];
    while (stack.length > 0) {
        var u = stack.pop();
        for (var j = 0; j < adj[u].length; j++) {
            var c = conversions[adj[u][j]];
            ans[c[1]] = mulMod(ans[u], c[2]);
            stack.push(c[1]);
        }
    }
    return ans;
};

// a * b mod p without leaving the 2^53 range a double holds exactly.
var mulMod = function(a, b) {
    var MOD = 1000000007;
    var hi = (a * Math.floor(b / 65536)) % MOD;
    return (hi * 65536 + a * (b % 65536)) % MOD;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More depth-first search problems

• Operations on Tree Medium
• Throne Inheritance Medium
• Implement Magic Dictionary Medium
• Design Add and Search Words Data Structure Medium
• Foldable Binary Tree Medium
• K-th Largest Perfect Subtree Size in Binary Tree Medium