Given a Tree consisting of N nodes having values in the range [0, N – 1] and (N – 1) edges, and two nodes X and Y, the task is to find the number of possible paths in the Tree such that the node X does not appear before the node Y in the path.
Examples:
Input: N = 5, A = 2, B = 0, Edges[][] = { {0, 1}, {1, 2}, {1, 3}, {0, 4} }
Output: 18
Explanation:
Since (X, Y) and (Y, X) are being considered different, so the count of all possible paths connecting any two pairs of vertices = 2 * 5C2 = 20.
Out of these 20 pairs, those paths cannot be chosen, which consist of both nodes 2 and 0 as well as Node 2 appearing before Node 0.
There are two such paths (colored as green) which are shown below:
So there are total 20 – 2 = 18 such paths.
Input: N = 9, X = 5, Y = 3, Edges[][] = { {0, 2}, {1, 2}, {2, 3}, {3, 4}, {4, 6}, {4, 5}, {5, 7}, {5, 8} }
Output: 60
Explanation:
Since (X, Y) and (Y, X) are being considered different, so the count of all possible paths connecting any two pairs of vertices = N * (N – 1) = 9 * 8 = 72.
On observing the diagram below, any path starting from a Node in the subtree of Node 5, denoted by black, connecting to the vertices passing through the Node 3, denoted by green, will always have 5 appearing before 3 in the path.
Therefore, total number of possible paths = (Total Nodes grouped in black) * (Total Nodes grouped in green) = 3 * 4 = 12.
Therefore, the final answer = 72 – 12 = 60
Approach:
The idea is to find the combination of node pairs that will always have the Node X appearing before Node Y in the path connecting them. Then, subtract the count of such pairs from the total number of possible node pairs = NC2. Consider node Y as the root node. Now any path which first encounters X and then Y, starts from the node in the subtree of node X and ends at a node in the sub-tree of node Y but not in the subtree of node W, where W is an immediate child of node Y and lies between X and Y in these paths.
Therefore, the final answer can be calculated by:
Count = N * (N – 1) – size_of_subtree(X) * (size_of_subtree(Y) – size_of_subtree(W))
If Y is taken as the root of the tree. Then, size_of_subtree(Y) = N.
Count = N * (N – 1) – size_of_subtree(X) * (N- size_of_subtree(W))
Follow the steps below to solve the problem:
- Initialize arrays subtree_size [], visited [] and check_subtree [] each of size N + 1. Initialize elements of visited [] as 0.
- Perform the DFS Traversal with Y as the root node to fill the check_subtree[] and subtree_size [] for each node. The check_subtree[] checks whether the subtree of the current node contains node X or not.
- Find the child(say node v) of Y which is in the path from X to Y. Initialize an integer variable say difference.
- Assign (total number of nodes – subtree_size[v] ) to difference.
- Return (N * (N – 1) ) – (subtree_size[A] * (difference)) as the answer.
Below is the implementation of the above approach:
C++
// C++ Program to implement// the above approach#include <bits/stdc++.h>#define int long long intusing namespace std;// Maximum number of nodesconst int NN = 3e5;// Vector to store the treevector<int> G[NN + 1];// Function to perform DFS Traversalint dfs(int node, int A, int* subtree_size, int* visited, int* check_subtree){ // Mark the node as visited visited[node] = true; // Initialize the subtree size // of each node as 1 subtree_size[node] = 1; // If the node is same as A if (node == A) { // Mark check_subtree[node] as true check_subtree[node] = true; } // Otherwise else check_subtree[node] = false; // Iterate over the adjacent nodes for (int v : G[node]) { // If the adjacent node // is not visited if (!visited[v]) { // Update the size of the // subtree of current node subtree_size[node] += dfs(v, A, subtree_size, visited, check_subtree); // Check if the subtree of // current node contains node A check_subtree[node] = check_subtree[node] | check_subtree[v]; } } // Return size of subtree of node return subtree_size[node];}// Function to add edges to the treevoid addedge(int node1, int node2){ G[node1].push_back(node2); G[node2].push_back(node1);}// Function to calculate the number of// possible pathsint numberOfPairs(int N, int B, int A){ // Stores the size of subtree // of each node int subtree_size[N + 1]; // Stores which nodes are // visited int visited[N + 1]; // Initialize all nodes as unvisited memset(visited, 0, sizeof(visited)); // Stores if the subtree of // a node contains node A int check_subtree[N + 1]; // DFS Call dfs(B, A, subtree_size, visited, check_subtree); // Stores the difference between // total number of nodes and // subtree size of an immediate // child of Y lies between the // path from A to B int difference; // Iterate over the adjacent nodes B for (int v : G[B]) { // If the node is in the path // from A to B if (check_subtree[v]) { // Calculate the difference difference = N - subtree_size[v]; break; } } // Return the final answer return (N * (N - 1)) - difference * (subtree_size[A]);}// Driver Codeint32_t main(){ int N = 9; int X = 5, Y = 3; // Insert Edges addedge(0, 2); addedge(1, 2); addedge(2, 3); addedge(3, 4); addedge(4, 6); addedge(4, 5); addedge(5, 7); addedge(5, 8); cout << numberOfPairs(N, Y, X); return 0;} |
Java
// Java Program to implement// the above approachimport java.util.*;class GFG{// Maximum number of nodesstatic int NN = (int) 3e5;// Vector to store the treestatic Vector<Integer> []G = new Vector[NN + 1];// Function to perform DFS Traversalstatic int dfs(int node, int A, int[] subtree_size, int[] visited, int[] check_subtree){ // Mark the node as visited visited[node] = 1; // Initialize the subtree size // of each node as 1 subtree_size[node] = 1; // If the node is same as A if (node == A) { // Mark check_subtree[node] as true check_subtree[node] = 1; } // Otherwise else check_subtree[node] = 0; // Iterate over the adjacent nodes for (int v : G[node]) { // If the adjacent node // is not visited if (visited[v] == 0) { // Update the size of the // subtree of current node subtree_size[node] += dfs(v, A, subtree_size, visited, check_subtree); // Check if the subtree of // current node contains node A check_subtree[node] = check_subtree[node] | check_subtree[v]; } } // Return size of subtree of node return subtree_size[node];}// Function to add edges to the treestatic void addedge(int node1, int node2){ G[node1].add(node2); G[node2].add(node1);}// Function to calculate the number of// possible pathsstatic int numberOfPairs(int N, int B, int A){ // Stores the size of subtree // of each node int []subtree_size = new int[N + 1]; // Stores which nodes are // visited int []visited = new int[N + 1]; // Stores if the subtree of // a node contains node A int []check_subtree = new int[N + 1]; // DFS Call dfs(B, A, subtree_size, visited, check_subtree); // Stores the difference between // total number of nodes and // subtree size of an immediate // child of Y lies between the // path from A to B int difference = 0; // Iterate over the adjacent nodes B for (int v : G[B]) { // If the node is in the path // from A to B if (check_subtree[v] > 0) { // Calculate the difference difference = N - subtree_size[v]; break; } } // Return the final answer return (N * (N - 1)) - difference * (subtree_size[A]);}// Driver Codepublic static void main(String[] args){ int N = 9; int X = 5, Y = 3; for (int i = 0; i < G.length; i++) G[i] = new Vector<Integer>(); // Insert Edges addedge(0, 2); addedge(1, 2); addedge(2, 3); addedge(3, 4); addedge(4, 6); addedge(4, 5); addedge(5, 7); addedge(5, 8); System.out.print(numberOfPairs(N, Y, X));}}// This code is contributed by sapnasingh4991 |
Python3
# Python3 program to implement# the above approach# Maximum number of nodesNN = int(3e5)# Vector to store the treeG = []for i in range(NN + 1): G.append([])# Function to perform DFS Traversaldef dfs(node, A, subtree_size, visited, check_subtree): # Mark the node as visited visited[node] = True # Initialize the subtree size # of each node as 1 subtree_size[node] = 1 # If the node is same as A if (node == A): # Mark check_subtree[node] as true check_subtree[node] = True # Otherwise else: check_subtree[node] = False # Iterate over the adjacent nodes for v in G[node]: # If the adjacent node # is not visited if (not visited[v]): # Update the size of the # subtree of current node subtree_size[node] += dfs(v, A, subtree_size, visited, check_subtree) # Check if the subtree of # current node contains node A check_subtree[node] = (check_subtree[node] | check_subtree[v]) # Return size of subtree of node return subtree_size[node]# Function to add edges to the treedef addedge(node1, node2): G[node1] += [node2] G[node2] += [node1]# Function to calculate the number of# possible pathsdef numberOfPairs(N, B, A): # Stores the size of subtree # of each node subtree_size = [0] * (N + 1) # Stores which nodes are # visited visited = [0] * (N + 1) # Stores if the subtree of # a node contains node A check_subtree = [0] * (N + 1) # DFS Call dfs(B, A, subtree_size, visited, check_subtree) # Stores the difference between # total number of nodes and # subtree size of an immediate # child of Y lies between the # path from A to B difference = 0 # Iterate over the adjacent nodes B for v in G[B]: # If the node is in the path # from A to B if (check_subtree[v]): # Calculate the difference difference = N - subtree_size[v] break # Return the final answer return ((N * (N - 1)) - difference * (subtree_size[A]))# Driver CodeN = 9X = 5Y = 3# Insert Edges addedge(0, 2)addedge(1, 2)addedge(2, 3)addedge(3, 4)addedge(4, 6)addedge(4, 5)addedge(5, 7)addedge(5, 8)# Function callprint(numberOfPairs(N, Y, X))# This code is contributed by Shivam Singh |
C#
// C# Program to implement// the above approachusing System;using System.Collections.Generic;class GFG{// Maximum number of nodesstatic int NN = (int) 3e5;// List to store the treestatic List<int> []G = new List<int>[NN + 1];// Function to perform DFS Traversalstatic int dfs(int node, int A, int[] subtree_size, int[] visited, int[] check_subtree){ // Mark the node as visited visited[node] = 1; // Initialize the subtree size // of each node as 1 subtree_size[node] = 1; // If the node is same as A if (node == A) { // Mark check_subtree[node] as true check_subtree[node] = 1; } // Otherwise else check_subtree[node] = 0; // Iterate over the adjacent nodes foreach (int v in G[node]) { // If the adjacent node // is not visited if (visited[v] == 0) { // Update the size of the // subtree of current node subtree_size[node] += dfs(v, A, subtree_size, visited, check_subtree); // Check if the subtree of // current node contains node A check_subtree[node] = check_subtree[node] | check_subtree[v]; } } // Return size of subtree of node return subtree_size[node];}// Function to add edges to the treestatic void addedge(int node1, int node2){ G[node1].Add(node2); G[node2].Add(node1);}// Function to calculate the number of// possible pathsstatic int numberOfPairs(int N, int B, int A){ // Stores the size of subtree // of each node int []subtree_size = new int[N + 1]; // Stores which nodes are // visited int []visited = new int[N + 1]; // Stores if the subtree of // a node contains node A int []check_subtree = new int[N + 1]; // DFS Call dfs(B, A, subtree_size, visited, check_subtree); // Stores the difference between // total number of nodes and // subtree size of an immediate // child of Y lies between the // path from A to B int difference = 0; // Iterate over the adjacent nodes B foreach (int v in G[B]) { // If the node is in the path // from A to B if (check_subtree[v] > 0) { // Calculate the difference difference = N - subtree_size[v]; break; } } // Return the readonly answer return (N * (N - 1)) - difference * (subtree_size[A]);}// Driver Codepublic static void Main(String[] args){ int N = 9; int X = 5, Y = 3; for (int i = 0; i < G.Length; i++) G[i] = new List<int>(); // Insert Edges addedge(0, 2); addedge(1, 2); addedge(2, 3); addedge(3, 4); addedge(4, 6); addedge(4, 5); addedge(5, 7); addedge(5, 8); Console.Write(numberOfPairs(N, Y, X));}}// This code is contributed by sapnasingh4991 |
Javascript
<script> // Javascript Program to implement the above approach // Maximum number of nodes let NN = 3e5; // Vector to store the tree let G = new Array(NN + 1); // Function to perform DFS Traversal function dfs(node, A, subtree_size, visited, check_subtree) { // Mark the node as visited visited[node] = 1; // Initialize the subtree size // of each node as 1 subtree_size[node] = 1; // If the node is same as A if (node == A) { // Mark check_subtree[node] as true check_subtree[node] = 1; } // Otherwise else check_subtree[node] = 0; // Iterate over the adjacent nodes for (let v = 0; v < G[node].length; v++) { // If the adjacent node // is not visited if (visited[G[node][v]] == 0) { // Update the size of the // subtree of current node subtree_size[node] += dfs(G[node][v], A, subtree_size, visited, check_subtree); // Check if the subtree of // current node contains node A check_subtree[node] = check_subtree[node] | check_subtree[G[node][v]]; } } // Return size of subtree of node return subtree_size[node]; } // Function to add edges to the tree function addedge(node1, node2) { G[node1].push(node2); G[node2].push(node1); } // Function to calculate the number of // possible paths function numberOfPairs(N, B, A) { // Stores the size of subtree // of each node let subtree_size = new Array(N + 1); subtree_size.fill(0); // Stores which nodes are // visited let visited = new Array(N + 1); visited.fill(0); // Stores if the subtree of // a node contains node A let check_subtree = new Array(N + 1); check_subtree.fill(0); // DFS Call dfs(B, A, subtree_size, visited, check_subtree); // Stores the difference between // total number of nodes and // subtree size of an immediate // child of Y lies between the // path from A to B let difference = 0; // Iterate over the adjacent nodes B for (let v = 0; v < G[B].length; v++) { // If the node is in the path // from A to B if (check_subtree[G[B][v]] > 0) { // Calculate the difference difference = N - subtree_size[G[B][v]]; break; } } // Return the final answer return (N * (N - 1)) - difference * (subtree_size[A]); } let N = 9; let X = 5, Y = 3; for (let i = 0; i < G.length; i++) G[i] = []; // Insert Edges addedge(0, 2); addedge(1, 2); addedge(2, 3); addedge(3, 4); addedge(4, 6); addedge(4, 5); addedge(5, 7); addedge(5, 8); document.write(numberOfPairs(N, Y, X));</script> |
Output:
60
Time Complexity: O(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!
