Problem Link https://dunjudge.me/analysis/problems/2052/

Problem in Simple Words:

You have a tree with N nodes and the i‘th node is associated with the value A[i]. When the value of a node i is >=X, it is called a special node. You have to process 2 types of queries.

  1. Input S and C and increase all the values A[j] where j is in the subtree of node S by a number C. Note that C is always non-negative.
  2. Input S. Print the number of pairs of nodes (i,j) such that both i and j are special nodes and the path from node i to node j passes through the edge from S to Par[S] where Par[S] corresponds to the parent of node S.

Problem Difficulty: Medium

Prerequisites:

Trees, DFS traversal, range query data structures like Segment Tree and BIT along with lazy propagation (The solution discussed below will use Segment Tree).

Quick Explanation:

Maintain two segment trees. One which performs operation 1 using lazy propagation and has a maximum query. For operation 2, keep another segment tree where each leaf has a 0 or 1 depending if the node is special or not along with a point update for marking nodes as special. For query 2, we just sum up a range of the 2nd segtree using the range of the subtree of S given. The answer is the product of the number of special nodes in the subtree of S and the number of special nodes excluding the subtree of S. We keep calling the max query while the value returned is >=X. The index of this value is then changed to INT_MIN in the lazy tree and it is marked as active in the 2nd segtree.

Detailed Explanation:

  • Tree to Array: We first convert the tree into an array where we can perform our lazy updates. This can be done with a simple DFS traversal. We keep track of the entry and exit index of each node in the array formed. This comes useful for query 1 as we now know which range to update in O(1) as we have precomputed it.
void dfs(int v, int p) //Tree to array and storing entry and exit indices.
{
    ord[tx] = a[v];
    tin[v] = tx++;
    for(int i=0; i<graph[v].size(); i++)
    {
        int u = graph[v][i];
        if(u==p) continue;   //Ensures we do not re-visit the parent
        dfs(u,v);
    }
    tout[v] = tx-1;
}
//Ord[] is the array we build our segment tree upon. 
//Tin[] stores the start points of all nodes and tout[] stores the exit points. 
//Tx is used as a pointer for which index is currently free. 
//A[]  stores the initial values of each node.
  • Build our segment trees: Segment trees are built the usual way The code for it can be seen in the link at the end. We build our lazy propagation tree on the array ord which contains the values of the nodes. The 2nd segment tree does not need any array to be built on as initially it is filled with 0s.
  • Compute the Queries: 
    • If the query is of type 1, we need a range update on the lazy tree in subtree of node S. We know the range of the subtree of S is (tin[S], tout[S]) as we have precomputed it. Hence we lazily update our tree.
    • If the query is of type 2, we first want to ensure all the special nodes have been marked in the 2nd segment tree before computing their sum. Therefore, we continuously call the max query on the lazy tree while the value returned is >=X. The classic maximum query in a lazy segtree is modified slightly to return a pair of the max value and the index of that max. If the max is >=X, we perform point update on the index in the 2nd tree and make its value as 1(it is special). We then update that index in the lazy tree to INT_MIN. This is because the range update queries are always non-negative. Therefore, a special node is always special. Making the index INT_MIN ensures that the same index will not be returned again as the special i.e >=X and we won’t have to update it again in the 2nd tree.
    • Though the while loop for query 2 makes the code look inefficient, the complexity of the loop will be O(N) over all queries as the maximum nodes do not get repeated once we update them to INT_MIN.
    • For query 2, we need to output the number of pairs (i,j) such that the condition given above is satisfied. Drawing a few examples, it can be seen that if (i,j) have to satisfy the given condition, then (i,j) both can’t be in the subtree of the node S nor can they both be in the part of the tree excluding the subtree of S. Therefore, of node (i,j) one resides in the subtree of S and the other resides outside the subtree of S. Hence, using simply combinatorics the number of pairs (i,j) possible is equal to the number of special nodes in subtree of S into the number of special nodes residing outside the subtree of S.
    • The usage of segment trees allows each query to be computed in O(log n).

Time Complexity: O(N + Q log N) =~ O(Q log n)

Github Code link: https://github.com/PyProjectsIsFun/Dunjudge/blob/master/smurf_paths.cpp

Banner vector created by roserodionova – www.freepik.com
Visits 172

One Reply to “Smurf Paths Dunjudge Editorial”

Leave a Reply

Your email address will not be published. Required fields are marked *