Multiplication queries in a tree

Question

We are given a tree of N nodes (1-N) with each node having an initial value A[i]. Tree is rooted at node 1.

We are given the Q queries of type :

1 V X : multiply all nodes in subtree of `X` with value `V`.
2 X   : find the value of node `X`.  

Constraints:

N <= 10^5
Q <= 10^5

My Approach :

Say, we have below tree as an input :

       1
     /  \
    2    3
   /  \   \
   4  5    7
  /
 6

The idea is to traverse the tree using **DFS** and construct a tree 
traversal array that contains two values for each node.


index        : 0 1 2 3 4 5 6
node         : 1 2 4 6 5 3 7
subtree-size : 7 4 2 1 1 2 1

 and then we create a `segment tree` using above array.

             (0-6)
         /           \
      (0-3)           (4-6)
   /       \         /     \
  (0-1)   (2-3)     (4-5)  (6)
 /   \     /   \    /   \
(0) (1)  (2) (3)   (4)  (5)

--> So now when we get a query of type-1 say, 1 3 2. 
we need to multiply all nodes in 2's sub-tree, which means we need to do a update 
query at (1-4) in our segment tree. 
At each node of a segment tree we keep a initial multiplication factor as 1 and 
update it by multiplying it with the value 'V (in this case = 3)' whenever we get the query of type 1.
--> When we get query of type - 2, say 2 4 : we can now query our 
segment tree at (2, 2) and consolidate all the multiplication factors 
in the path and multiply it with the existing value of node '4' to return the
 result of the query.

With this approach each query can be solved using time O(log(n)). I was not able to code this approach on time.

Is there any other simpler approach to solve this problem (maybe without using seg-tree) and as per the constraints query time should be at-least as efficient as O(log(n)) time.

Answer 1

Algorithm

First perform some preprocessing to build the tree:

• Build an adjacency list from the edges
• Perform a depth-first traversal using the adjacency list, starting at the root, and so identifying which is the parent of each node. This can be stored in an array such that parents[i] holds the index of the parent of node i, if it exists, or -1 if it has no parent. The latter is only true for the root.
• Create an array to store the multiplication factor per node, initialised to 1 for each node.

Then execute the queries:

• If the query is of type 1, multiply the factor already known for the given node with the given value. This takes constant time.
• If the query is of type 2, accumulate the factors found on the path from the given node to the root (use parents array). Finally output the product of this accumulated factor and the (original) value of the given node. This has a O(logn) average time complexity.

Example

Here is an example input (which really you should have provided!), but it is 0-index based, as this is more common in programming languages. So the root node is identified with index 0:

values: [2, 1, 4, 9, 3, 5]
edges: [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5]]
queries: [
    [2, 2],
    [1, 3, 2],
    [2, 5],
    [1, 10, 0],
    [2, 5],
    [2, 1],
]

This represents the following tree:

               2
             /   \
            1     4
           / \   /
          9   3 5

When all queries have been executed, the tree could be represented like this, where each node is accompanied by a factor:

               2(10)
             /   \
            1     4(3)
           / \   /
          9   3 5

The expected output for the queries would be:

4
15
150
10

Implementation

Below is an example implementation in JavaScript. Again, this is using 0-based indexes. It runs the above example input.

// Helper function for building the adjacency list
function dfs(adj, parents, node) {
    for (let child of adj[node]) {
        if (parents[child] == -2) { // Not yet visited
            parents[child] = node;
            dfs(adj, parents, child);
        }
    }
}

// Main function to create the adjacency list
function prepare(values, edges) {
    let adj = values.map(value => []); // For each node an empty list (vector)
    
    // Populate the adjacency lists from the given edges
    for (let [u, v] of edges) {
        // Register edge in two directions
        adj[u].push(v);
        adj[v].push(u);
    }
    
    let parents = Array(values.length).fill(-2); // Parents are unknown
    parents[0] = -1; // It is a given that the root is at 0: it has no parent
    dfs(adj, parents, 0); // Identify all other parents
    return parents;
}

// Two functions for performing two types of queries
function multiply(values, parents, factors, factor, i) {
    factors[i] *= factor;
}

function calculate(values, parents, factors, i) {
    let factor = 1; 
    // Walk up the tree to accumulate the applicable factors
    for (let j = i; j > -1; j = parents[j]) {
        factor *= factors[j];
    }
    return values[i] * factor;
}

function solve(values, edges, queries) {
     // Preprocessing:
    let parents = prepare(values, edges);
    let factors = Array(values.length).fill(1); // All factors start as 1
    // Execute the queries:
    for (let query of queries) {
        if (query[0] == 1) {
            multiply(values, parents, factors, query[1], query[2]);
        } else {
            let value = calculate(values, parents, factors, query[1]);
            console.log(value);
        }
    }
}

// Example input:
let values = [2, 1, 4, 9, 3, 5];
let edges = [[0, 1], [0, 2], [1, 3], [1, 4], [2, 5]];
let queries = [
    [2, 2],  // => 4
    [1, 3, 2],
    [2, 5], // => 15 (=5*3)
    [1, 10, 0],
    [2, 5], // => 150 (=5*3*10)
    [2, 1], // => 10 (1*10)
];

solve(values, edges, queries);