5 weeks ago

John 910

Hyderabad

Question 1

Make Pairs in an Array

Question 2

Tree Maximum

12 weeks ago

Ayush Gangwani 1.2k

New Delhi

Solution to Problem 2

Analysis

The problem requires the direct application of Euler Tour Technique or flattening of Trees. The idea is to flatten the tree in an array so that the subtree of every node is represented by some subarray in the array obtained after flattening the tree. We can then use a Fenwick Tree (BIT) or a Segment Tree to answer the required queries efficiently.

The flattening of a tree is essentially doing a DFS ( Depth First Search ) and recording the order in which we visit the nodes in the form of an array. The following pseudoCode achieves the same, we just append a node in the tour array as soon as we visit it for the first time and store the time instants at which we reach a node and the time when we have visited the entire subtree of the node in the in and out arrays respectively.

adj[N][], in[N], out[N], tour[N]
timer = -1

flatten(node, par)
{
    in[node] = ++timer;
    tour[in[node]] = val[node]; 
    for nbr in adj[node]:
        if(nbr!=par) flatten(child,node);
    out[node] = timer;
}

Let's understand the flattening of a tree in brief with an example:

Before the DFS, our in and out arrays are initialized with zeros. In this visualization, the first row represents the node indices, the second row represents in, and the third represents out.

Current timer value: 0

Since we call dfs(1,0) , we reach a new node and hence we increment the timer, then we set in[1] to the current timer value of 0. Then, we proceed to call dfs(2, 1) and dfs(3, 1).

Current timer value: 1

Now we must resolve dfs(2, 1) and dfs(3, 1). It does not matter which order we process these in, so for this example, we start with dfs(2, 1). We then increment the timer and hence set in[2] to 1. However, because node 2 has no children, we don't call dfs. Instead, we set out[2] to 1 because our current timer is now 1.

Current timer value: 2

Now we must resolve dfs(3, 1). Similar to before, we increment the timer and set in[3] to the value of the timer (2 in this case). Then, we proceed to make the calls dfs(4, 3) and dfs(5, 3).

Current timer value: 3

Now we must resolve dfs(4, 3) and dfs(5, 3). First, we resolve dfs(4, 3) by incrementing the timer and setting in[4] to the value of the timer (3 in this case). Then, since node 4 has no children, set out[4] to 3.

Current timer value: 4

Now, we must resolve dfs(5, 3). Similar to before, we increment the timer and set in[5] to 4. Since node 5 also has no children, set out[5] to 4.

Now, we backtrack our way through the dfs calls. We first encounter and resolve node 3, setting out[3] to 4. We then do the same for node 1, setting out[1] to 4. Our DFS traversal is now complete.

Now, we can see that the tree is flattened into the array tour and that the subtree of some node i is represented by the subarray tour[in[i],out[i]]. We can now build a BIT/Segment Tree over the flattened array and answer the queries accordingly. The following pseudoCode skips over the implementation details and provides an overview of the solution.

PseudoCode

solve(tree, queries):
    arr = flatten(tree)
    root = new BIT(arr)
    for query in queries:
        if(query.type == 1):
            root.update(query.node, query.x)
        else:
            print(root.max(in[query.node],out[query.node]))

18 months ago

Jigyansu • 60

IIT Delhi

I solved it using segment tree on flattened tree. The tutorial says we can also use BIT for range queries. I might be wrong, but I think BIT can be used with prefix queries only and range queries if and only if the function is non-idempotent (such as sum , multiplication). But since range-max query is idempotent, I am not sure how calculation of [L, R] max will work in fenwick tree.