You are given an n-ary tree with a special property:
If we burst a random node of the tree, this node along with its immediate parents up to the root vanishes. The tree has N nodes and nodes are numbered from 1 to N. The root is always at 1. Given a sequence of queries denoting the number of the node we start bursting, the problem is to find the number of subtrees that would be formed in the end according to the above property, for each query independently.
Examples:
Input:
Consider the following tree:
1
/ | \
2 3 4
/ \ \
5 6 7
/ \
8 9
q = 2
n = 1
n = 7
Output:
3
4
Explanation:
In the first query after bursting node 1, there
will be 3 subtrees formed rooted at 2, 3 and 4.
In the second query after bursting node 7, nodes
4 and 1 also get burst, thus there will
be 4 subtrees formed rooted at 8, 9, 2 and 3.
Since we are dealing with n-ary tree we can use a representation similar to that of a graph, and add the bidirectional edges in an array of lists. Now if we burst a node, we can say for sure that all its children will become separate subtrees. Moreover all the children of its parents and others ancestors till the root that burst, will also become separate subtrees. So in our final answer we want to exclude the current node and all its ancestors in the path till the root. Thus we can form the equation to solve as:
answer[node] = degree[node] + allChild[parent[node]] – countPath[node]
where allChild[]: number of node’s children + number of its
parent’s children + ..+ number of root’s children
parent[]: parent of a node in the tree
degree[]: number of children for a node
countPath[]: number of nodes from root to parent of node
We can fill all the above arrays using depth first search over the adjacency list.We can start from the root 1, assuming its parent is 0 and recur depth first to propagate its values to its children. Thus we can pre-process and fill the above arrays initially and return the equation’s value for each query accordingly.
Following is the implementation of the above approach:
C++
// C++ program to find number of subtrees after bursting nodes#include <bits/stdc++.h>using namespace std;// do depth first search of node nod; par is its parentvoid dfs(int nod, int par, list<int> adj[], int allChild[], int parent[], int degree[], int countPath[]){ // go through the adjacent nodes for (auto it = adj[nod].begin(); it != adj[nod].end(); it++) { int curr = *it; // avoid cycling if (curr == par) continue; degree[nod]++; countPath[curr] = countPath[nod] + 1; parent[curr] = nod; } // propagated from parent allChild[nod] = allChild[parent[nod]] + degree[nod]; // go through the adjacent nodes for (auto it = adj[nod].begin(); it != adj[nod].end(); it++) { int curr = *it; // avoid cycling if (curr == par) continue; // recur and go depth first dfs(curr, nod, adj, allChild, parent, degree, countPath); }}// Driver codeint main(){ int n = 9; // adjacency list for each node list<int> adj[n + 1]; // allChild[]: number of node's children + number of its // parent's children + ..+ number of root's children // parent[]: parent of a node in the tree // degree[]: number of children for a node // countPath[]: number of nodes from root to parent of node int allChild[n + 1] = { 0 }, parent[n + 1] = { 0 }, degree[n + 1] = { 0 }, countPath[n + 1] = { 0 }; // construct tree adj[1].push_back(2); adj[2].push_back(1); adj[1].push_back(3); adj[3].push_back(1); adj[1].push_back(4); adj[4].push_back(1); adj[3].push_back(5); adj[5].push_back(3); adj[3].push_back(6); adj[6].push_back(3); adj[4].push_back(7); adj[7].push_back(4); adj[7].push_back(8); adj[8].push_back(7); adj[7].push_back(9); adj[9].push_back(7); // assume 1 is root and 0 is its parent dfs(1, 0, adj, allChild, parent, degree, countPath); // 2 queries int curr = 1; cout << degree[curr] + allChild[parent[curr]] - countPath[curr] << endl; curr = 7; cout << degree[curr] + allChild[parent[curr]] - countPath[curr] << endl; return 0;} |
Java
// Java program to find number of subtrees// after bursting nodesimport java.util.*;class GFG{// Do depth first search of node nod;// par is its parentstatic void dfs(int nod, int par, List<Integer> adj[], int allChild[], int parent[], int degree[], int countPath[]){ // Go through the adjacent nodes for(int it : adj[nod]) { int curr = it; // astatic void cycling if (curr == par) continue; degree[nod]++; countPath[curr] = countPath[nod] + 1; parent[curr] = nod; } // Propagated from parent allChild[nod] = allChild[parent[nod]] + degree[nod]; // Go through the adjacent nodes for(int it : adj[nod]) { int curr = it; // astatic void cycling if (curr == par) continue; // recur and go depth first dfs(curr, nod, adj, allChild, parent, degree, countPath); }}// Driver codepublic static void main(String[] args){ int n = 9; // Adjacency list for each node @SuppressWarnings("unchecked") List<Integer> []adj = new List[n + 1]; for(int i = 0; i < adj.length; i++) adj[i] = new Vector<Integer>(); // allChild[]: number of node's children + // number of its parent's children + ..+ // number of root's children // parent[]: parent of a node in the tree // degree[]: number of children for a node // countPath[]: number of nodes from root // to parent of node int []allChild = new int[n + 1]; int []parent = new int[n + 1]; int []degree = new int[n + 1]; int []countPath = new int[n + 1]; // Contree adj[1].add(2); adj[2].add(1); adj[1].add(3); adj[3].add(1); adj[1].add(4); adj[4].add(1); adj[3].add(5); adj[5].add(3); adj[3].add(6); adj[6].add(3); adj[4].add(7); adj[7].add(4); adj[7].add(8); adj[8].add(7); adj[7].add(9); adj[9].add(7); // Assume 1 is root and 0 is its parent dfs(1, 0, adj, allChild, parent, degree, countPath); // 2 queries int curr = 1; System.out.print(degree[curr] + allChild[parent[curr]] - countPath[curr] + "\n"); curr = 7; System.out.print(degree[curr] + allChild[parent[curr]] - countPath[curr] + "\n");}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program to find number of # subtrees after bursting nodes# Do depth first search of node # nod par is its parentdef dfs(nod, par, adj, allChild, parent, degree, countPath): # Go through the adjacent nodes for it in adj[nod]: curr = it # Avoid cycling if (curr == par): continue degree[nod] += 1 countPath[curr] = countPath[nod] + 1 parent[curr] = nod # Propagated from parent allChild[nod] = (allChild[parent[nod]] + degree[nod]) # Go through the adjacent nodes for it in adj[nod]: curr = it # Avoid cycling if (curr == par): continue # recur and go depth first dfs(curr, nod, adj, allChild, parent, degree, countPath)# Driver codeif __name__ == '__main__': n = 9 # Adjacency list for each node adj = [[] for i in range(n + 1)] # allChild: number of node's children + number of its # parent's children + ..+ number of root's children # parent: parent of a node in the tree # degree: number of children for a node # countPath: number of nodes from root to parent of node allChild, parent = [0] * (n + 1), [0] * (n + 1) degree, countPath = [0] * (n + 1), [0] * (n + 1) # Construct tree adj[1].append(2) adj[2].append(1) adj[1].append(3) adj[3].append(1) adj[1].append(4) adj[4].append(1) adj[3].append(5) adj[5].append(3) adj[3].append(6) adj[6].append(3) adj[4].append(7) adj[7].append(4) adj[7].append(8) adj[8].append(7) adj[7].append(9) adj[9].append(7) # Assume 1 is root and 0 is its parent dfs(1, 0, adj, allChild, parent, degree, countPath) # 2 queries curr = 1 print(degree[curr] + allChild[parent[curr]] - countPath[curr]) curr = 7 print(degree[curr] + allChild[parent[curr]] - countPath[curr])# This code is contributed by mohit kumar 29 |
C#
// C# program to find number of subtrees// after bursting nodesusing System;using System.Collections.Generic;class GFG{// Do depth first search of node nod;// par is its parentstatic void dfs(int nod, int par, List<int> []adj, int []allChild, int []parent, int []degree, int []countPath){ // Go through the adjacent nodes foreach(int it in adj[nod]) { int curr = it; // astatic void cycling if (curr == par) continue; degree[nod]++; countPath[curr] = countPath[nod] + 1; parent[curr] = nod; } // Propagated from parent allChild[nod] = allChild[parent[nod]] + degree[nod]; // Go through the adjacent nodes foreach(int it in adj[nod]) { int curr = it; // astatic void cycling if (curr == par) continue; // recur and go depth first dfs(curr, nod, adj, allChild, parent, degree, countPath); }}// Driver codepublic static void Main(String[] args){ int n = 9; // Adjacency list for each node List<int> []adj = new List<int>[n + 1]; for(int i = 0; i < adj.Length; i++) adj[i] = new List<int>(); // allChild[]: number of node's children + // number of its parent's children + ..+ // number of root's children // parent[]: parent of a node in the tree // degree[]: number of children for a node // countPath[]: number of nodes from root // to parent of node int []allChild = new int[n + 1]; int []parent = new int[n + 1]; int []degree = new int[n + 1]; int []countPath = new int[n + 1]; // Contree adj[1].Add(2); adj[2].Add(1); adj[1].Add(3); adj[3].Add(1); adj[1].Add(4); adj[4].Add(1); adj[3].Add(5); adj[5].Add(3); adj[3].Add(6); adj[6].Add(3); adj[4].Add(7); adj[7].Add(4); adj[7].Add(8); adj[8].Add(7); adj[7].Add(9); adj[9].Add(7); // Assume 1 is root and 0 is its parent dfs(1, 0, adj, allChild, parent, degree, countPath); // 2 queries int curr = 1; Console.Write(degree[curr] + allChild[parent[curr]] - countPath[curr] + "\n"); curr = 7; Console.Write(degree[curr] + allChild[parent[curr]] - countPath[curr] + "\n");}}// This code is contributed by Amit Katiyar |
Javascript
<script>// Javascript program to find number of subtrees// after bursting nodes // Do depth first search of node nod;// par is its parent function dfs(nod,par,adj,allChild,parent,degree,countPath) { // Go through the adjacent nodes for(let it=0;it<adj[nod].length;it++) { let curr = adj[nod][it]; // astatic void cycling if (curr == par) continue; degree[nod]++; countPath[curr] = countPath[nod] + 1; parent[curr] = nod; } // Propagated from parent allChild[nod] = allChild[parent[nod]] + degree[nod]; // Go through the adjacent nodes for(let it=0;it<adj[nod].length;it++) { let curr = adj[nod][it]; // astatic void cycling if (curr == par) continue; // recur and go depth first dfs(curr, nod, adj, allChild, parent, degree, countPath); } } // Driver code let n = 9; // Adjacency list for each node let adj = new Array(n + 1); for(let i = 0; i < adj.length; i++) adj[i] = []; // allChild[]: number of node's children + // number of its parent's children + ..+ // number of root's children // parent[]: parent of a node in the tree // degree[]: number of children for a node // countPath[]: number of nodes from root // to parent of node let allChild = new Array(n + 1); let parent = new Array(n + 1); let degree = new Array(n + 1); let countPath = new Array(n + 1); for(let i=0;i<n+1;i++) { allChild[i]=0; parent[i]=0; degree[i]=0; countPath[i]=0; } // Contree adj[1].push(2); adj[2].push(1); adj[1].push(3); adj[3].push(1); adj[1].push(4); adj[4].push(1); adj[3].push(5); adj[5].push(3); adj[3].push(6); adj[6].push(3); adj[4].push(7); adj[7].push(4); adj[7].push(8); adj[8].push(7); adj[7].push(9); adj[9].push(7); // Assume 1 is root and 0 is its parent dfs(1, 0, adj, allChild, parent, degree, countPath); // 2 queries let curr = 1; document.write(degree[curr] + allChild[parent[curr]] - countPath[curr] + "<br>"); curr = 7; document.write(degree[curr] + allChild[parent[curr]] - countPath[curr] + "<br>"); // This code is contributed by unknown2108</script> |
Output
3 4
The time complexity of the above algorithm is O(E * lg(V)) where E is the number of edges and V is the number of vertices.
Auxiliary Space: O(n) where n is the number of nodes.
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!
