Given an N-ary Tree rooted at 1, and an array val[] consisting of weights assigned to every node, and a matrix Q[][], consisting of queries of the form {X, D}, the task for each query is to find the minimum of all weights assigned to the nodes which are atmost at a distance D from the node X. Examples:
Input: Q[][] = {{1, 2}, {2, 1}}, val[] = {1, 2, 3, 3, 5}
1 / \ 4 5 / 3 / 2Output: 1 3 Explanation: Query 1: X = 1, D = 2 The nodes atmost at a distance 2 from the node 1 are {1, 3, 4, 5} and the weights assigned to these nodes are {1, 3, 3, 5} respectively. Therefore, the minimum weight assigned is 1. Query 2: X = 2, D = 1 The nodes atmost at a distance 1 from node 2 is {2, 3} and the weights assigned to these nodes are {2, 3} respectively. Therefore, the minimum weight assigned is 2. Input: Q[][] = {{1, 2}}, val[] = {1, 2, 4}
1 / \ 2 3Output: 1
Naive Approach: The simplest approach to solve each query is to iterate the tree and find all the nodes which are at most at a distance D from node X and find the minimum of all the weights assigned to these nodes. Time Complexity: O(Q * N) Auxiliary Space: O(1) Efficient Approach: To optimize the above approach, follow the steps below:
- Implement the Euler Tour of the tree and assign an index to each node of the tree.
- Now at every index, store the depth and value associated with the node in an array.
- Build Merge Sort Tree on the array and Sort the range according to the depth of the nodes.
- For each query, it’s known that all the nodes of the subtree of X lie between in[X] and out[X] arrays where in and out are the index at which the nodes perform DFS.
- In this range, find the minimum weighted node having a distance of at most D. Build the Merge Sort Tree and merge the two ranges according to the increasing order of depth and find the prefix minimum among the values at every node of the Merge Sort Tree.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>using namespace std;const int INF = 1e9 + 9;/// Function to perform DFsvoid dfs(int a, int par, int dep, vector<vector<int> >& v, vector<int>& depth, vector<int>& in, vector<int>& out, vector<pair<int, int> >& inv, vector<int>& val, int& tim){ // Assign depth depth[a] = dep; // Assign in-time in[a] = ++tim; // Store depth and value to // construct Merge Sort Tree inv[tim] = make_pair(depth[a], val[a]); for (int i : v[a]) { // Skip the parent if (i == par) continue; dfs(i, a, dep + 1, v, depth, in, out, inv, val, tim); } // Assign out-time out[a] = tim;}// Function to build the Merge Sort Treevoid build(int node, int l, int r, vector<vector<pair<int, int> > >& segtree, vector<pair<int, int> >& inv){ // If the current node is // a leaf node if (l == r) { segtree[node].push_back(inv[l]); return; } int mid = (l + r) >> 1; // Recursively build left and right subtree build(2 * node + 1, l, mid, segtree, inv); build(2 * node + 2, mid + 1, r, segtree, inv); // Merge left and right node // of merge sort tree merge(segtree[2 * node + 1].begin(), segtree[2 * node + 1].end(), segtree[2 * node + 2].begin(), segtree[2 * node + 2].end(), back_inserter(segtree[node])); int mn = INF; for (auto& i : segtree[node]) { // Compute the prefix minimum mn = min(mn, i.second); i.second = mn; }}// Function to solve each queryint query(int x, int y, int dep, int node, int l, int r, vector<vector<pair<int, int> > >& segtree){ // Check for no overlap if (l > y || r < x || x > y) return INF; // Condition for complete overlap if (x <= l && r <= y) { // Find the node with // depth greater than d; auto it = upper_bound(segtree[node].begin(), segtree[node].end(), make_pair(dep, INF)); if (it == segtree[node].begin()) // Return if the first depth // is greater than d return INF; // Decrement the pointer; it--; // Return prefix minimum return it->second; } int mid = (l + r) >> 1; int a = query(x, y, dep, 2 * node + 1, l, mid, segtree); int b = query(x, y, dep, 2 * node + 2, mid + 1, r, segtree); return min(a, b);}// Function to compute the queriesvoid answerQueries(vector<pair<int, int> > queries, vector<vector<int> >& v, vector<int> val, int n){ // Stores the time int tim = 0; // Stores the in and out time vector<int> in(n + 10), out(n + 10); // Stores depth vector<int> depth(n + 10); vector<pair<int, int> > inv(n + 10); dfs(1, 0, 0, v, depth, in, out, inv, val, tim); // Merge sort tree to store // depth of each node vector<vector<pair<int, int> > > segtree(4 * n + 10); // Construct the merge sort tree build(0, 1, tim, segtree, inv); for (auto& i : queries) { int x = i.first; int dep = depth[x] + i.second; // Find the minimum value in subtree of x // and subtree of x lies from in[x] // to out[x] in merge sort tree int minVal = query(in[x], out[x], dep, 0, 1, tim, segtree); cout << minVal << endl; }}// Driver Codeint main(){ /* 1 / \ 4 5 / 3 / 2 */ int n = 5; // Stores the graph vector<vector<int> > v(n + 1); // Stores the weights vector<int> val(n + 1); // Assign edges v[1].push_back(4); v[4].push_back(1); v[1].push_back(5); v[5].push_back(1); v[4].push_back(3); v[3].push_back(4); v[3].push_back(2); v[2].push_back(3); // Assign weights val[1] = 1; val[2] = 3; val[3] = 2; val[4] = 3; val[5] = 5; // Stores the queries vector<pair<int, int> > queries = { { 1, 2 }, { 2, 1 } }; answerQueries(queries, v, val, n); return 0;} |
Python3
# Python code addition import sysINF = int(1e9 + 9)x_ = 1y_ = 3# Function to perform DFSdef dfs(a, par, dep, v, depth, in_, out, inv, val, tim): # Assign depth depth[a] = dep # Assign in-time in_[a] = tim tim += 1 # Store depth and value to construct Merge Sort Tree inv.append((depth[a], val[a])) for i in v[a]: # Skip the parent if i == par: continue dfs(i, a, dep + 1, v, depth, in_, out, inv, val, tim) # Assign out-time out[a] = tim tim += 1# Function to build the Merge Sort Treedef build(node, l, r, segtree, inv): # If the current node is a leaf node if l == r: segtree[node].append(inv[l]) return mid = (l + r) // 2 # Recursively build left and right subtree build(2 * node + 1, l, mid, segtree, inv) build(2 * node + 2, mid + 1, r, segtree, inv) # Merge left and right node of merge sort tree segtree[node] = sorted(segtree[2 * node + 1] + segtree[2 * node + 2]) mn = INF for i in range(len(segtree[node])): # Compute the prefix minimum mn = min(mn, segtree[node][i][1]) segtree[node][i] = (segtree[node][i][0], mn)# Function to solve each querydef query(x, y, dep, node, l, r, segtree): # Check for no overlap if l > y or r < x or x > y: return INF # Condition for complete overlap if x <= l and r <= y: # Find the node with depth greater than d; it = upper_bound(segtree[node], (dep, INF)) if it == segtree[node][0]: # Return if the first depth is greater than d return INF # Decrement the pointer it -= 1 # Return prefix minimum return it[1] mid = (l + r) // 2 a = query(x, y, dep, 2 * node + 1, l, mid, segtree) b = query(x, y, dep, 2 * node + 2, mid + 1, r, segtree) return min(a, b)# Function to compute the queriesdef answerQueries(queries, v, val, n): # Stores the time tim = 0 # Stores the in and out time in_ = [0] * (n + 10) out = [0] * (n + 10) print(x_) # Stores depth depth = [0] * (n + 10) print(y_) inv = [] return dfs(1, 0, 0, v, depth, in_, out, inv, val, tim) # Merge sort tree to store depth of each node segtree = [[] for _ in range(4 * n + 10)] # Construct the merge sort tree build(0, 1, tim, segtree, inv) for i in queries: x = i[0] dep = depth[x] + i[1] minVal = query(in_[x], out[x], dep, 0, 1, tim, segtree) print(minVal) n = 5# Stores the graphv = [[] for _ in range(n+1)]# Stores the weightsval = [0]*(n+1)# Assign edgesv[1].append(4)v[4].append(1)v[1].append(5)v[5].append(1)v[4].append(3)v[3].append(4)v[3].append(2)v[2].append(3)# Assign weightsval[1] = 1val[2] = 3val[3] = 2val[4] = 3val[5] = 5# Stores the queriesqueries = [(1, 2), (2, 1)]answerQueries(queries, v, val, n)# The code is contributed by Nidhi goel. |
Output:
1 3
Time Complexity: O(N * log(N) + Q * log(N)) Auxiliary Space: O(N * log N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
