Given a Generic Tree consisting of N nodes numbered from 0 to N – 1 which is rooted at node 0 and an array val[] such that the value at each node is represented by val[i], the task for each node is to find the value of MEX of its subtree.
The MEX value of node V is defined as the smallest missing positive number in a tree rooted at node V.
Examples:
Input: N = 6, edges = {{0, 1}, {1, 2}, {0, 3}, {3, 4}, {3, 5}}, val[] = {4, 3, 5, 1, 0, 2}
Output: [6, 0, 0, 3, 1, 0]
Explanation:
0(4)
/ \
1(3) 3(1)
/ / \
2(5) 4(0) 5(2)In the subtrees of:
Node 0: All the values in range [0, 5] are present, hence the smallest non-negative value not present is 6.
Node 1: The smallest non-negative value not present in subtree of node 1 is 0.
Node 2: The smallest non-negative value not present in subtree of node 2 absent is 0.
Node 3: All the values in range [0, 2] are present, hence the smallest non-negative value not present in subtree of node 3 is 3.
Node 4: The smallest non-negative value not present in subtree of node 4 is 1.
Node 5: The smallest non-negative value not present in subtree of node 5 is 0.
Approach: The given problem can be solved using DFS Traversal on the given Tree and performing the Binary Search to find the missing minimum positive integers in each node subtree. Follow the steps below to solve the problem:
- Initialize an array, say sol[] to store the MEX for each node.
- Perform the DFS Traversal from node 0 and perform the following steps:
- Store all the nodes during DFS for each node in the vector.
- Merge the two vectors in the sorted order for each node in the recursive calls.
- Apply binary search on the sorted list to find the smallest non-negative integer value which is not present in the sorted array and store the value of MEX of the current subtree in the array sol[].
- After completing the above steps, print the value stored in the array sol[] as the result.
Below is the implementation of the above approach:
C++14
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Stores the edges of the treevector<vector<int> > edges;// Function to add edgesvoid add_edge(int x, int y){ edges.push_back({ x, y });}// Function to merge two sorted vectorsvector<int> merge(vector<int>& a, vector<int>& b){ // To store the result vector<int> res; int i = 0, j = 0; int n = a.size(), m = b.size(); // Iterating both vectors while (i < n && j < m) { if (a[i] < b[j]) res.push_back(a[i++]); else if (b[j] < a[i]) res.push_back(b[j++]); } // Pushing remaining elements of // vector a while (i < n) res.push_back(a[i++]); // Pushing remaining elements of // vector b while (j < m) res.push_back(b[j++]); return res;}// Function to perform the DFS Traversal// that returns the subtree of node// in sorted mannervector<int> help(vector<int> tree[], int x, int p, vector<int>& c, vector<int>& sol){ vector<int> res; res.push_back(c[x]); // Iterate the childrens for (auto i : tree[x]) { // All values of subtree // i in sorted manner if (i != p) { vector<int> tmp = help(tree, i, x, c, sol); res = merge(res, tmp); } } int l = 0, r = res.size() - 1; int ans = res.size(); // Binary search to find MEX while (l <= r) { // Find the mid int mid = (l + r) / 2; // Update the ranges if (res[mid] > mid) r = mid - 1; else { ans = mid + 1; l = mid + 1; } } if (res[0] != 0) ans = 0; // Update the MEX for the current // tree node sol[x] = ans; return res;}// Function to find MEX of each// subtree of treevoid solve(int A, vector<int> C){ int n = A; vector<int> tree[n + 1]; for (auto i : edges) { tree[i[0]].push_back(i[1]); tree[i[1]].push_back(i[0]); } vector<int> sol(n, 0); // Function Call help(tree, 0, -1, C, sol); // Print the ans for each nodes for (auto i : sol) cout << i << " ";}// Driver Codeint main(){ int N = 6; add_edge(0, 1); add_edge(1, 2); add_edge(0, 3); add_edge(3, 4); add_edge(3, 5); vector<int> val = { 4, 3, 5, 1, 0, 2 }; solve(N, val); return 0;} |
Java
// Java program for the above approachimport java.util.ArrayList;import java.util.Arrays;public class GFG { // Stores the edges of the tree static ArrayList<int[]> edges = new ArrayList<int[]>(); // Function to add edges static void add_edge(int x, int y) { edges.add(new int[] { x, y }); } // Function to merge two sorted vectors static ArrayList<Integer> merge(ArrayList<Integer> a, ArrayList<Integer> b) { // To store the result ArrayList<Integer> res = new ArrayList<Integer>(); int i = 0, j = 0; int n = a.size(), m = b.size(); // Iterating both vectors while (i < n && j < m) { if (a.get(i) < b.get(j)) res.add(a.get(i++)); else if (b.get(j) < a.get(i)) res.add(b.get(j++)); } // Pushing remaining elements of // vector a while (i < n) res.add(a.get(i++)); // Pushing remaining elements of // vector b while (j < m) res.add(b.get(j++)); return res; } // Function to perform the DFS Traversal // that returns the subtree of node // in sorted manner static ArrayList<Integer> help(ArrayList<Integer>[] tree, int x, int p, int[] c, int[] sol) { ArrayList<Integer> res = new ArrayList<Integer>(); res.add(c[x]); // Iterate the childrens for (int i : tree[x]) { // All values of subtree // i in sorted manner if (i != p) { ArrayList<Integer> tmp = help(tree, i, x, c, sol); res = merge(res, tmp); } } int l = 0, r = res.size() - 1; int ans = res.size(); // Binary search to find MEX while (l <= r) { // Find the mid int mid = (l + r) / 2; // Update the ranges if (res.get(mid) > mid) r = mid - 1; else { ans = mid + 1; l = mid + 1; } } if (res.get(0) != 0) ans = 0; // Update the MEX for the current // tree node sol[x] = ans; return res; } // Function to find MEX of each // subtree of tree @SuppressWarnings("unchecked") static void solve(int A, int[] C) { int n = A; ArrayList<Integer>[] tree = new ArrayList[n + 1]; for (int i = 0; i <= n; i++) tree[i] = new ArrayList<Integer>(); for (int[] i : edges) { tree[i[0]].add(i[1]); tree[i[1]].add(i[0]); } int[] sol = new int[n]; // Function Call help(tree, 0, -1, C, sol); // Print the ans for each nodes for (int i : sol) System.out.print(i + " "); } // Driver Code public static void main(String[] args) { int N = 6; add_edge(0, 1); add_edge(1, 2); add_edge(0, 3); add_edge(3, 4); add_edge(3, 5); int[] val = { 4, 3, 5, 1, 0, 2 }; solve(N, val); }}// This code is contributed by Lovely Jain |
Python3
# Python code for the above approachfrom typing import List# Stores the edges of the treeedges = []# Function to add edgesdef add_edge(x: int, y: int): edges.append([x, y])# Function to merge two sorted listsdef merge(a: List[int], b: List[int]) -> List[int]: # To store the result res = [] i, j = 0, 0 n, m = len(a), len(b) # Iterating both lists while i < n and j < m: if a[i] < b[j]: res.append(a[i]) i += 1 elif b[j] < a[i]: res.append(b[j]) j += 1 # Pushing remaining elements of # list a while i < n: res.append(a[i]) i += 1 # Pushing remaining elements of # list b while j < m: res.append(b[j]) j += 1 return res# Function to perform the DFS Traversal# that returns the subtree of node# in sorted manner (continued)def help(tree: List[List[int]], x: int, p: int, c: List[int], sol: List[int]) -> List[int]: res = ] # Iterate the childrens for i in tree[x]: # All values of subtree # i in sorted manner if i != p: tmp = help(tree, i, x, c, sol) res = merge(res, tmp) l, r = 0, len(res) - 1 ans = len(res) # Binary search to find MEX while l <= r: # Find the mid mid = (l + r) // 2 # Update the ranges if res[mid] > mid: r = mid - 1 else: ans = mid + 1 l = mid + 1 if res[0] != 0: ans = 0 # Update the MEX for the current # tree node sol[x] = ans return res# Function to find MEX of each# subtree of treedef solve(A: int, C: List[int]): n = A tree = [[] for _ in range(n + 1)] for i in edges: tree[i[0]].append(i[1]) tree[i[1]].append(i[0]) sol = [0] * n # Function Call help(tree, 0, -1, C, sol) # Print the ans for each nodes for i in sol: print(i, end=' ')# Example usageN = 6add_edge(0, 1)add_edge(1, 2)add_edge(0, 3)add_edge(3, 4)add_edge(3, 5)val = [4, 3, 5, 1, 0, 2]solve(N, val)# This code is contributed by Potta Lokesh |
C#
// C# Equivalent Codeusing System;using System.Collections.Generic;namespace GFG{ class Program { // Stores the edges of the tree static List<int[]> edges = new List<int[]>(); // Function to add edges static void add_edge(int x, int y) { edges.Add(new int[] { x, y }); } // Function to merge two sorted vectors static List<int> merge(List<int> a, List<int> b) { // To store the result List<int> res = new List<int>(); int i = 0, j = 0; int n = a.Count, m = b.Count; // Iterating both vectors while (i < n && j < m) { if (a[i] < b[j]) res.Add(a[i++]); else if (b[j] < a[i]) res.Add(b[j++]); } // Pushing remaining elements of // vector a while (i < n) res.Add(a[i++]); // Pushing remaining elements of // vector b while (j < m) res.Add(b[j++]); return res; } // Function to perform the DFS Traversal // that returns the subtree of node // in sorted manner static List<int> help(List<int>[] tree, int x, int p, int[] c, int[] sol) { List<int> res = new List<int>(); res.Add(c[x]); // Iterate the childrens foreach (int i in tree[x]) { // All values of subtree // i in sorted manner if (i != p) { List<int> tmp = help(tree, i, x, c, sol); res = merge(res, tmp); } } int l = 0, r = res.Count - 1; int ans = res.Count; // Binary search to find MEX while (l <= r) { // Find the mid int mid = (l + r) / 2; // Update the ranges if (res[mid] > mid) r = mid - 1; else { ans = mid + 1; l = mid + 1; } } if (res[0] != 0) ans = 0; // Update the MEX for the current // tree node sol[x] = ans; return res; } // Function to find MEX of each // subtree of tree static void solve(int A, int[] C) { int n = A; List<int>[] tree = new List<int>[n + 1]; for (int i = 0; i <= n; i++) tree[i] = new List<int>(); foreach (int[] i in edges) { tree[i[0]].Add(i[1]); tree[i[1]].Add(i[0]); } int[] sol = new int[n]; // Function Call help(tree, 0, -1, C, sol); // Print the ans for each nodes foreach (int i in sol) Console.Write(i + " "); } // Driver Code public static void Main(string[] args) { int N = 6; add_edge(0, 1); add_edge(1, 2); add_edge(0, 3); add_edge(3, 4); add_edge(3, 5); int[] val = { 4, 3, 5, 1, 0, 2 }; solve(N, val); } }} |
Javascript
<script>// Javascript program for the above approach// Stores the edges of the treelet edges = [];// Function to add edgesfunction add_edge(x, y) { edges.push([x, y]);}// Function to merge two sorted vectorsfunction merge(a, b) { // To store the result let res = []; let i = 0, j = 0; let n = a.length, m = b.length; // Iterating both vectors while (i < n && j < m) { if (a[i] < b[j]) res.push(a[i++]); else if (b[j] < a[i]) res.push(b[j++]); } // Pushing remaining elements of // vector a while (i < n) res.push(a[i++]); // Pushing remaining elements of // vector b while (j < m) res.push(b[j++]); return res;}// Function to perform the DFS Traversal// that returns the subtree of node// in sorted mannerfunction help(tree, x, p, c, sol) { let res = []; res.push(c[x]); // Iterate the childrens for (let i of tree[x]) { // All values of subtree // i in sorted manner if (i != p) { let tmp = help(tree, i, x, c, sol); res = merge(res, tmp); } } let l = 0, r = res.length - 1; let ans = res.length; // Binary search to find MEX while (l <= r) { // Find the mid let mid = Math.floor((l + r) / 2); // Update the ranges if (res[mid] > mid) r = mid - 1; else { ans = mid + 1; l = mid + 1; } } if (res[0] != 0) ans = 0; // Update the MEX for the current // tree node sol[x] = ans; return res;}// Function to find MEX of each// subtree of treefunction solve(A, C) { let n = A; let tree = new Array(n + 1).fill(0).map(() => []); for (let i of edges) { tree[i[0]].push(i[1]); tree[i[1]].push(i[0]); } let sol = new Array(n).fill(0); // Function Call help(tree, 0, -1, C, sol); // Print the ans for each nodes for (let i of sol) document.write(i + " ");}// Driver Codelet N = 6;add_edge(0, 1);add_edge(1, 2);add_edge(0, 3);add_edge(3, 4);add_edge(3, 5);let val = [4, 3, 5, 1, 0, 2];solve(N, val);// This code is contributed by _saurabh_jaiswal.</script> |
Output
6 0 0 3 1 0
Time Complexity: O(N*(N + log N))
Auxiliary Space: O(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!
