Given a tree of N nodes numbered from 1 to N and N-1 edges, and an array V[] of length N denoting the value of the ith node (0 ? i ? n-1). The task is to calculate the number of simple paths starting with node 1.
A path is defined as a simple path if the frequency of the value of any one of the nodes in the path is at least half of the length of the path rounded down to the next greater integer. The length of a path from A to node B is the number of nodes you encounter in that unique path while going from A to B.
Example:
Input: N = 5, Edges[][] = {{1, 2}, {2, 4}, {2, 5}, {5, 3}}, V[] = {7, 9, 9, 4, 8};
Output: 3
Explanation: ALL THE POSSIBLE PATHS ARE:
- Path= 1, length of path = 1, maximum frequent element is with val 7 with frequency 1, 1 ? (1/2).
- Path= 1->2, length of path = 2, maximum frequent element is with 7 Â with frequency 1, 1 ? (2/2).
- Path= 1->2->5->3, length of path = 4, maximum frequent element is with val 9 with frequency 2, (2 ? 4/2).
Approach:Â
The idea is to use store the frequency of every node while traversing the path starting from the root node and check whether the frequency of the current node value is greater than equal to half of the length of the path.
Follow the steps below to solve the problem:
- Start dfs with node 1.
- Maintain a frequency map to store the frequency of value of all the element’s values coming in the path.
- Maintain a variable ‘len’ that store the number of nodes in the current node.
- Let’s suppose the maximum frequency (maximum frequent element value) at a node x, is f, now the maximum frequency at children (y) of a node x is maximum(f, frequency[y] ).
- After iterating all the children of a node, decreasing the frequency of the current node value before returning from a node as this node will not contribute further.
Below is the implementation of the above approach:
C++
// C++ program to Count// Simple Paths in given TreeÂ
#include <bits/stdc++.h>using namespace std;Â
// Function to traverse the given tree using DFSint DFS(int len, int V[], int root, int parent, int f,        int& ans, unordered_map<int, int>& freq,        unordered_map<int, vector<int> >& graph){    len++;    int val = V[root - 1];Â
    // Frequency map    freq[val]++;Â
    int newfreq = max(f, freq[val]);    int requirefreq = (len + 1) / 2;Â
    if (newfreq >= requirefreq)        ans++;    f = newfreq;Â
    for (auto it : graph[root]) {        if (it != parent) {            DFS(len, V, it, root, f, ans, freq, graph);        }    }    freq[val]--;}Â
// Wrapper function to call dfs functionint FindTotalPath(int n, int edges[][2], int V[]){    // Adjacency list    unordered_map<int, vector<int> > graph;    for (int i = 0; i < n - 1; i++) {        graph[edges[i][0]].push_back(edges[i][1]);        graph[edges[i][1]].push_back(edges[i][0]);    }    unordered_map<int, int> freq;    int ans = 0;    DFS(0, V, 1, -1, 0, ans, freq, graph);    return ans;}Â
// Driver Codeint main(){    int N = 5;    int edges[][2]        = { { 1, 2 }, { 2, 4 }, { 2, 5 }, { 5, 3 } };    int V[] = { 7, 9, 9, 4, 8 };    // Function Call    cout << FindTotalPath(N, edges, V) << endl;} |
Java
// Java program to Count// Simple Paths in given Treeimport java.util.*;Â
class GFG {Â
  // Function to traverse the given tree using DFS  static int    DFS(int len, int V[], int root, int parent, int f,        HashMap<Integer, Integer> freq,        HashMap<Integer, ArrayList<Integer> > graph)  {    len++;    int val = V[root - 1];Â
    // Frequency map    freq.put(val, freq.getOrDefault(val, 0) + 1);Â
    int newfreq = Math.max(f, freq.get(val));    int requirefreq = (len + 1) / 2;    int ans = 0;    if (newfreq >= requirefreq)      ans++;    f = newfreq;    System.out.println(requirefreq);    for (Integer it : graph.get(root)) {      if (it != parent) {        ans += DFS(len, V, it, root, f, freq,                   graph);      }    }    freq.put(val, freq.get(val) - 1);    return ans;  }Â
  // Wrapper function to call dfs function  static int FindTotalPath(int n, int edges[][], int V[])  {         // Adjacency list    HashMap<Integer, ArrayList<Integer> > graph      = new HashMap<>();    for (int i = 0; i <= n; i++) {      graph.put(i, new ArrayList<>());    }    for (int i = 0; i < n - 1; i++) {      graph.get(edges[i][0]).add(edges[i][1]);      graph.get(edges[i][1]).add(edges[i][0]);    }    HashMap<Integer, Integer> freq = new HashMap<>();    int ans = DFS(0, V, 1, -1, 0, freq, graph);    return ans;  }Â
  // Driver code  public static void main(String[] args)  {    int N = 5;    int edges[][]      = { { 1, 2 }, { 2, 4 }, { 2, 5 }, { 5, 3 } };    int V[] = { 7, 9, 9, 4, 8 };Â
    // Function Call    System.out.println(FindTotalPath(N, edges, V));  }}Â
// This code is contributed by karandeep1234. |
Python3
# Function to traverse the given tree using DFSdef dfs(len,V,root,parent,f,freq,graph):    len = len+1;    val = V[root-1];         # Frequency Map    if val in freq:        freq[val] = freq[val]+1    else:        freq[val] = 1;    newfreq = max(f,freq[val])    requirefreq = (len+1)//2    ans = 0    if newfreq >= requirefreq :        ans = ans + 1    f = newfreq    for it in graph[root]:        if it != parent:            ans += dfs(len,V,it,root,f,freq,graph);    freq[val] = freq[val]-1;    return ans# Wrapper Function to call dfs functiondef FindTotalPath(n,edges,V):    # Adjacency List    graph = dict()    for i in range(0,n+1):        graph[i] = []    for i in range(n-1):        graph[edges[i][0]].append(edges[i][1])        graph[edges[i][1]].append(edges[i][0])    freq = {}    ans = dfs(0,V,1,-1,0,freq,graph)    return ansN = 5edges =[[1,2],[2,4],[2,5],[5,3]]V = [7,9,9,4,8]print(FindTotalPath(N,edges,V))Â
# This code is contributed by anskalyan3. |
C#
// C# program to Count// Simple Paths in given Treeusing System;using System.Collections.Generic;class GFG{Â
  // Function to traverse the given tree using DFS  static int    DFS(int len, int[] V, int root, int parent, int f,        Dictionary<int, int> freq,        Dictionary<int, List<int>> graph)  {    len++;    int val = V[root - 1];Â
    // Frequency map    freq[val] = freq.GetValueOrDefault(val, 0) + 1;Â
    int newfreq = Math.Max(f, freq[val]);    int requirefreq = (len + 1) / 2;    int ans = 0;    if (newfreq >= requirefreq)      ans++;    f = newfreq;Â
    foreach (int it in graph[root])    {      if (it != parent)      {        ans += DFS(len, V, it, root, f, freq,                   graph);      }    }    freq[val] = freq[val] - 1;    return ans;  }Â
  // Wrapper function to call dfs function  static int FindTotalPath(int n, int[,] edges, int[] V)  {Â
    // Adjacency list    Dictionary<int, List<int>> graph      = new Dictionary<int, List<int>>();    for (int i = 0; i <= n; i++)    {      graph[i] = new List<int>();    }    for (int i = 0; i < n - 1; i++)    {      graph[edges[i, 0]].Add(edges[i, 1]);      graph[edges[i, 1]].Add(edges[i, 0]);    }    Dictionary<int, int> freq = new Dictionary<int, int>();    int ans = DFS(0, V, 1, -1, 0, freq, graph);    return ans;  }Â
  // Driver code  public static void Main()  {    int N = 5;    int[,] edges      = { { 1, 2 }, { 2, 4 }, { 2, 5 }, { 5, 3 } };    int[] V = { 7, 9, 9, 4, 8 };Â
    // Function Call    Console.Write(FindTotalPath(N, edges, V));  }}Â
// This code is contributed by Saurabh Jaiswal |
Javascript
// Javascript program to Count// Simple Paths in given TreeÂ
// Function to traverse the given tree using DFSfunction DFS(len, V, root, parent, f, freq, graph) {Â Â Â Â len++;Â Â Â Â let val = V[root - 1];Â
    // Frequency map    freq.set(val, freq.get(val) + 1);Â
    let newfreq = Math.max(f, freq.get(val));    let requirefreq = Math.floor((len + 1) / 2);Â
    let ans = 0;    if (newfreq >= requirefreq) {        ans++;    }    f = newfreq;Â
    for (let it = 0; it < graph.get(root).length; it++) {        if (graph.get(root)[it] != parent) {            ans += DFS(len, V, graph.get(root)[it], root, f/*,ans*/, freq,                graph);        }    }    freq.set(val, freq.get(val) - 1);    return ans;}Â
// Wrapper function to call dfs functionfunction FindTotalPath(n, edges, V) {    // Adjacency list    let graph = new Map();    for (let i = 0; i <= n; i++) {        graph.set(i, new Array());    }    for (let i = 0; i < n - 1; i++) {        let abc1 = graph.get(edges[i][0]);        let abc2 = graph.get(edges[i][1]);        abc1.push(edges[i][1]);        graph.set(edges[i][0], abc1);        abc2.push(edges[i][0]);        graph.set(edges[i][1], abc2);    }    let freq = new Map();    for (let i = 0; i <= n * 2; i++) {        freq.set(i, 0);    }    let ans = DFS(0, V, 1, -1, 0, freq, graph);    return ans;}Â
// Driver Codelet N = 5;let edges    = [[1, 2], [2, 4], [2, 5], [5, 3]];let V = [7, 9, 9, 4, 8];Â
// Function Callconsole.log(FindTotalPath(N, edges, V));Â
// This code is contributed by akashish__ |
Output
3
Time Complexity: O(N), Visiting every node a single time in a tree with N nodes
Auxiliary Space: O(N), Frequency map to store the frequency of the node value.
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!
