Skip to content
thecscience
THECSICENCE

Learn everything about computer science

  • Home
  • Human values
  • NCERT Solutions
  • HackerRank solutions
    • HackerRank Algorithms problems solutions
    • HackerRank C solutions
    • HackerRank C++ solutions
    • HackerRank Java problems solutions
    • HackerRank Python problems solutions
thecscience
THECSICENCE

Learn everything about computer science

HackerRank Cut Tree Problem Solution

Yashwant Parihar, July 2, 2023August 1, 2024

In this post, we will solve HackerRank Cut Tree Problem Solution.

Given a tree T with n nodes, how many subtrees (T’) of T have at most K edges connected to (T – T’)?

Input Format

The first line contains two integers n and K followed by n-1 lines each containing two integers a & b denoting that there’s an edge between a & b.

Constraints

1 <= K <= n <= 50
Every node is indicated by a distinct number from 1 to n.

Output Format

A single integer which denotes the number of possible subtrees.

Sample Input

3 1
2 1
2 3

Sample Output

6

Explanation

There are 2^3 possible sub-trees:

{} {1} {2} {3} {1, 2} {1, 3} {2, 3} {1, 2, 3}

But:
the sub-trees {2} and {1,3} are not valid. {2} isn’t valid because it has 2 edges connecting to it’s complement {1,3} whereas K = 1 in the sample test-case {1,3} isn’t valid because, well, it’s not a sub-tree. The nodes aren’t connected.

HackerRank Cut Tree Problem Solution
HackerRank Cut Tree Problem Solution

Cut Tree C Solution

#include <stdio.h>
#include <stdlib.h>
void dfs(int x,int parent);
int table[50][50]={0},c[50]={0},p[50],q[51]={0},N;
long long dp1[50][51]={0},dp2[50][51]={0},temp[51],ans; // 1 without 2 with [node][K]
int main(){
  int K,x,y,i,j,k;
  scanf("%d%d",&N,&K);
  for(i=0;i<N-1;i++){
    scanf("%d%d",&x,&y);
    table[x-1][y-1]=-1;
    table[y-1][x-1]=-1;
  }
  dfs(0,0);
  for(i=0;i<N;i++)
    if(!c[i])
      q[++q[0]]=i;
  while(q[0]){
    x=q[q[0]--];
    dp1[x][0]=dp2[x][0]=1;
    for(i=0;i<N;i++)
      if(table[x][i]==1){
        for(j=1;j<=K;j++)
          temp[j]=0;
        for(j=1;j<=K;j++){
          dp1[x][j]+=dp1[i][j]+dp2[i][j-1];
          for(k=0;k<=j;k++)
            if(k==1)
              temp[j]+=(dp2[i][k]+1)*dp2[x][j-k];
            else
              temp[j]+=dp2[i][k]*dp2[x][j-k];
        }
        for(j=1;j<=K;j++)
          dp2[x][j]=temp[j];
      }
    if(x){
      c[p[x]]--;
      if(!c[p[x]])
        q[++q[0]]=p[x];
    }
  }
  for(i=0,ans=0;i<=K;i++)
    ans+=dp1[0][i]+dp2[0][i];
  printf("%lld",ans);
  return 0;
}
void dfs(int x,int parent){
  int i;
  p[x]=parent;
  for(i=0;i<N;i++)
    if(table[x][i] && i!=parent){
      table[x][i]+=2;
      c[x]++;
      dfs(i,x);
    }
  return;
}

Cut Tree C++ Solution

#include <bits/stdc++.h>

using namespace std;

vector<string> split_string(string);

/*
 * Complete the cuttree function below.
 */
pair<vector<long>, vector<long> > br(const vector<vector<int> >& g, int i, int i0)
{
    vector<long> w(1, 1), wo;
    for (auto j: g[i]) if (j != i0)
    {
        auto [wp, wop] = br(g, j, i);
        if (wop.size() > wo.size()) wo.resize(wop.size(), 0);
        for (int i = 0; i < wop.size(); ++i) wo[i] += wop[i];
        if (wp.size() + 1 > wo.size()) wo.resize(wp.size() + 1, 0);
        for (int i = 0; i < wp.size(); ++i) wo[i+1] += wp[i];
        vector<long> w2(max(1+int(w.size()), int(wp.size() + w.size()) - 1), 0);
        for (int i = 0; i < w.size(); ++i)
        {
            w2[i+1] += w[i];
            for (int k = 0; k < wp.size(); ++k) w2[i+k] += w[i]*wp[k];
        }
        swap(w, w2);
    }
    return {w, wo};
}

long cutTree(int n, int k, vector<vector<int>> edges) {
    /*
     * Write your code here.
     */
    vector<vector<int> > g(n);
    for (auto& v: edges)
    {
        --v[0]; --v[1];
        g[v[0]].push_back(v[1]);
        g[v[1]].push_back(v[0]);
    }
    auto [w, wo] = br(g, 0, -1);
    for (auto k: w) cout << k << " "; cout << "\n";
    for (auto k: wo) cout << k << " "; cout << "\n";
    long res = 0;
    for (int i = 0; i < min<int>(w.size(), k+1); ++i) res += w[i];
    for (int i = 0; i < min<int>(wo.size(), k+1); ++i) res += wo[i];
    return res+1;
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    string nk_temp;
    getline(cin, nk_temp);

    vector<string> nk = split_string(nk_temp);

    int n = stoi(nk[0]);

    int k = stoi(nk[1]);

    vector<vector<int>> edges(n-1);
    for (int edges_row_itr = 0; edges_row_itr < n-1; edges_row_itr++) {
        edges[edges_row_itr].resize(2);

        for (int edges_column_itr = 0; edges_column_itr < 2; edges_column_itr++) {
            cin >> edges[edges_row_itr][edges_column_itr];
        }

        cin.ignore(numeric_limits<streamsize>::max(), '\n');
    }

    long result = cutTree(n, k, edges);

    fout << result << "\n";

    fout.close();

    return 0;
}

vector<string> split_string(string input_string) {
    string::iterator new_end = unique(input_string.begin(), input_string.end(), [] (const char &x, const char &y) {
        return x == y and x == ' ';
    });

    input_string.erase(new_end, input_string.end());

    while (input_string[input_string.length() - 1] == ' ') {
        input_string.pop_back();
    }

    vector<string> splits;
    char delimiter = ' ';

    size_t i = 0;
    size_t pos = input_string.find(delimiter);

    while (pos != string::npos) {
        splits.push_back(input_string.substr(i, pos - i));

        i = pos + 1;
        pos = input_string.find(delimiter, i);
    }

    splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1));

    return splits;
}

Cut Tree C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

class Solution {
    private class Node {
        public int Id { get; set; }
        public List<Node> Children { get; set; }
    }

    /*
     * Complete the cuttree function below.
     */
    static long cutTree(int n, int k, int[][] edges) {
        var dp = new long[n, k + 1];
        var graph = new List<int>[n];
        
        for (var i = 0; i < n; ++i) {
            graph[i] = new();
        }
        
        foreach (var edge in edges) {
            var u = edge[0] - 1;
            var v = edge[1] - 1;
            graph[u].Add(v);
            graph[v].Add(u);
        }

        var rootNode = new Node {
            Id = 0,
            Children = new()
        };
        
        BuildTree(graph, rootNode, -1);
        
        return Solve(rootNode, dp, k) + 1;
    }
    
    private static void BuildTree(List<int>[] graph, Node curNode, int parentNodeId) {
        foreach (var childNodeId in graph[curNode.Id].Where(n => n != parentNodeId)) {
            var childNode = new Node {
                Id = childNodeId,
                Children = new()
            };
            curNode.Children.Add(childNode);
            BuildTree(graph, childNode, curNode.Id);
        }
    }
    
    private static long Solve(Node node, long[,] dp, int k) {
        if (node.Children.Count == 0) {
            dp[node.Id, 0] = 1;
            return 1;
        }
        
        var ans = 0L;
        
        foreach (var childNode in node.Children) {
            ans += Solve(childNode, dp, k);
        }
        
        var dp2 = new long[k + 1, node.Children.Count];
        
        for (var i = 0; i <= k; ++i) {
            dp2[i, 0] = dp[node.Children[0].Id, i];
            
            if (i == 1) {
                ++dp2[i, 0];
            }
            
            for (var j = 1; j < node.Children.Count; ++j) {
                for (var k2 = 0; k2 <= i; ++k2) {
                    var extra = i - k2 == 1 ? 1 : 0;
                    dp2[i, j] += dp2[k2, j - 1] * (dp[node.Children[j].Id, i - k2] + extra);
                }
            }
            
            dp[node.Id, i] = dp2[i, node.Children.Count - 1];
            
            if (i < k || node.Id == 0) {
                ans += dp[node.Id, i];
            }
        }
        
        return ans;
    }

    static void Main(string[] args) {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        string[] nk = Console.ReadLine().Split(' ');

        int n = Convert.ToInt32(nk[0]);

        int k = Convert.ToInt32(nk[1]);

        int[][] edges = new int[n-1][];

        for (int edgesRowItr = 0; edgesRowItr < n-1; edgesRowItr++) {
            edges[edgesRowItr] = Array.ConvertAll(Console.ReadLine().Split(' '), edgesTemp => Convert.ToInt32(edgesTemp));
        }

        var result = 0L;

        checked {
            result = cutTree(n, k, edges);
        }
        
        textWriter.WriteLine(result);

        textWriter.Flush();
        textWriter.Close();
    }
}

Cut Tree Java Solution

import java.io.*;
import java.util.*;

public class cuttree extends PrintWriter {
    cuttree() { super(System.out, true); }
    Scanner sc = new Scanner(System.in);
    public static void main(String[] $) {
        cuttree o = new cuttree(); o.main(); o.flush();
    }

    int[] eo; int[][] ej;
    void append(int i, int j) {
        int o = eo[i]++;
        if (o >= 2 && (o & o - 1) == 0)
            ej[i] = Arrays.copyOf(ej[i], o << 1);
        ej[i][o] = j;
    }
    long[][] dp; long[] tt; int k;
    void init(int n) {
        eo = new int[n]; ej = new int[n][2];
        dp = new long[n][k + 1]; tt = new long[k + 1];
    }
    void mult(long[] aa, long[] bb) {
        Arrays.fill(tt, 0);
        for (int i = 0; i <= k; i++)
            for (int j = 0; i + j <= k; j++)
                tt[i + j] += aa[i] * bb[j];
        System.arraycopy(tt, 0, aa, 0, k + 1);
    }
    long ans = 1;
    void dfs(int p, int i) {
        dp[i][0] = 1;
        for (int o = eo[i]; o-- > 0; ) {
            int j = ej[i][o];
            if (j != p) {
                dfs(i, j);
                dp[j][1]++;
                mult(dp[i], dp[j]);
            }
        }
        for (int h = p == -1 ? k : k - 1; h >= 0; h--)
            ans += dp[i][h];
    }
    void main() {
        int n = sc.nextInt();
        if (n == 1) {
            println(2);
            return;
        }
        k = sc.nextInt();
        if (k == n)
            k = n - 1;
        init(n);
        for (int h = 0; h < n - 1; h++) {
            int i = sc.nextInt() - 1;
            int j = sc.nextInt() - 1;
            append(i, j);
            append(j, i);
        }
        dfs(-1, 0);
        println(ans);
    }
}

Cut Tree Python Solution

line = input().split()
n = int(line[0])
K = int(line[1])

adjlst = [[1]]
for i in range(n):
    adjlst.append([])
adjlst[1].append(0)

for i in range(n - 1):
    line = input().split()
    x = int(line[0])
    y = int(line[1])
    adjlst[x].append(y)
    adjlst[y].append(x)

def dfs(node, par, adjlst, K):
    conlst = [0] * (K + 1)
    dislst = [0] * (K + 1)
    conlst[0] = 1
    for chld in adjlst[node]:
        if chld != par:
            tcl, tdl = dfs(chld, node, adjlst, K)
            # print(str(tcl))
            # print(str(tdl))
            dislst[0] += tdl[0]
            tcl2 = [0] * (K + 1)
            for i in range(K):
                dislst[i + 1] += tcl[i] + tdl[i + 1]
                tcl2[i + 1] += conlst[i]
            for i in range(K + 1):
                for j in range(K + 1):
                    if i + j <= K:
                        tcl2[i + j] += tcl[i] * conlst[j]
            conlst = list(tcl2)
    return conlst, dislst

conlst, dislst = dfs(1, 0, adjlst, K)
# print(str(conlst))
# print(str(dislst))
ans = sum(conlst) + sum(dislst) + 1
print(str(ans))
c C# C++ HackerRank Solutions java python CcppCSharpHackerrank Solutionsjavapython

Post navigation

Previous post
Next post
  • HackerRank Dynamic Array Problem Solution
  • HackerRank 2D Array – DS Problem Solution
  • Hackerrank Array – DS Problem Solution
  • Von Neumann and Harvard Machine Architecture
  • Development of Computers
©2025 THECSICENCE | WordPress Theme by SuperbThemes