# HackerRank Cut Tree problem solution

In this HackerRank Cut, Tree problem solution we have given a tree T with n nodes, how many subtrees (T') of T have at most K edges connected to (T - T')?

## Problem solution in Python.

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

for i in range(n):

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

conlst = [0] * (K + 1)
dislst = [0] * (K + 1)
conlst[0] = 1
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))
```

{"mode":"full","isActive":false}

## Problem solution in Java.

```// practice with kaiboy
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);
}
}
```

{"mode":"full","isActive":false}

## Problem solution in C++.

```#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include<climits>
#include <numeric>
using namespace std;

class Tree {
int n_;
std::vector<std::vector<int>> edges;
std::vector<int64_t> cut;
std::vector<std::vector<int64_t>> connect;

void dfs(int u, int p, int k) {
connect[u][0] = 1;
for (auto& v : edges[u]) {
if (v == p) {
continue;
}
dfs(v, u, k);
for (int ku = k; ku >= 0; --ku) {
int64_t sum = 0;
for (int kv = 0; kv <= ku; ++kv) {
sum += connect[u][ku-kv] * (connect[v][kv] + (kv == 1 ? 1 : 0));
}
connect[u][ku] = sum;
}
}
cut[u] = std::accumulate(connect[u].begin(), connect[u].begin() + k, 0ll);
}

public:
Tree(int n): n_(n), edges(n) {
}
void add(int u, int v) {
edges[u].push_back(v);
edges[v].push_back(u);
}
int64_t cutWays(int k) {
cut.assign(n_, 0);
connect.assign(n_, std::vector<int64_t>(k+1));
dfs(0, 0, k);
cut[0] += connect[0][k];
return 1 + std::accumulate(cut.begin(), cut.end(), 0ll);
}
};

int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
for (int n, k, u, v; std::cin >> n >> k; ) {
Tree tree(n);
for (int i = 0; i < n - 1; ++i) {
std::cin >> u >> v;
}
std::cout << tree.cutWays(k) << std::endl;
}

return 0;
}
```

{"mode":"full","isActive":false}

## Problem solution in C.

```#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;
}```

{"mode":"full","isActive":false}