# Cut Tree

### Problem Statement :

```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.```

### Solution :

```                            ```Solution in C :

In C++ :

#include<iostream>
#include<string.h>
using namespace std;

#define MAXN 100
int first[MAXN], next1[MAXN], v[MAXN];
int edgeindex;
int n, k;
long long dp[MAXN][MAXN];
bool vis[MAXN];

{
v[edgeindex] = b;
next1[edgeindex] = first[a];
first[a] = edgeindex++;
}

void solve(int cur, int root)
{
if(vis[cur])
return;

for(int i = first[cur]; i != -1; i = next1[i])
{
if(v[i] == root)
continue;
solve(v[i], cur);
for(int j = k; j > 0; --j)
{
int tmp = 0;
for(int x = j; x > 0; x--)
{
dp[cur][j] += dp[cur][j-x] * dp[v[i]][x];
}
dp[cur][j] += dp[cur][j-1];
}
}
return;
}

int main()
{
while(cin>>n>>k)
{
edgeindex = 0;
memset(first, -1, sizeof(first));
memset(dp, 0, sizeof(dp));
memset(vis, false, sizeof(vis));
int a, b;
for(int i = 1; i < n; ++i)
{
cin>>a>>b;
}

for(int i = 1; i <= n; ++i)
{
dp[i][0] = 1;
}

solve(1, -1);

long long ans = 0;
for(int i = 1; i <= n; ++i)
{
for(int j = 0; j < k; ++j)
{
ans += dp[i][j];
}
}
ans += dp[1][k];
cout<<ans+1<<endl;
}
}

In Java :

import java.io.BufferedInputStream;
import java.util.ArrayList;
import java.util.Scanner;

public class Solution {
static long rooted[][] = new long [55][55];
static int size[] = new int[55];
static int outDegree[] = new int[55];
static ArrayList<Integer> tree[] = new ArrayList[55];
static int n;
static int k;

static void dfs(int u, int p) {
size[u] = 1;

for (int v : tree[u]) {
if (v == p) continue;
dfs(v, u);

outDegree[u]++;
size[u] += size[v];
}
//////////////////////////////////////////////////////////////////
long pre[] = rooted[u];
rooted[u][0] = 1;
for (int v : tree[u]) {
if (v == p) continue;

rooted[u] = new long[55];
for (int i=0; i<=k; i++) {
if (i >= 1) rooted[u][i] += pre[i - 1];
for (int j=0; j<=i; j++)
rooted[u][i] += pre[i - j] * rooted[v][j];
}
pre = rooted[u];
}
}

public static void main(String[] args) {
Scanner cin = new Scanner(new BufferedInputStream(System.in));
n = cin.nextInt();
k = cin.nextInt();
for (int i=0; i<n; i++) tree[i] = new ArrayList<Integer>();
for (int i=0; i<n-1; i++) {
int u = cin.nextInt(); u--;
int v = cin.nextInt(); v--;
}

dfs(0, -1);

long ans = 0;
for (int i=0; i<n; i++)
if (i == 0)
for (int j=0; j<=k; j++) ans += rooted[i][j];
else
for (int j=1; j<=k; j++) ans += rooted[i][j - 1];
System.out.println(ans + 1);

//		for (int i=0; i<n; i++) {
//			for (int j=0; j<=k; j++)
//				System.out.print(rooted[i][j] + " ");
//			System.out.println();
//		}
//		System.out.println();
}
}

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

In Python3 :

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))```
```

## Delete a Node

Delete the node at a given position in a linked list and return a reference to the head node. The head is at position 0. The list may be empty after you delete the node. In that case, return a null value. Example: list=0->1->2->3 position=2 After removing the node at position 2, list'= 0->1->-3. Function Description: Complete the deleteNode function in the editor below. deleteNo

## Print in Reverse

Given a pointer to the head of a singly-linked list, print each data value from the reversed list. If the given list is empty, do not print anything. Example head* refers to the linked list with data values 1->2->3->Null Print the following: 3 2 1 Function Description: Complete the reversePrint function in the editor below. reversePrint has the following parameters: Sing

Given the pointer to the head node of a linked list, change the next pointers of the nodes so that their order is reversed. The head pointer given may be null meaning that the initial list is empty. Example: head references the list 1->2->3->Null. Manipulate the next pointers of each node in place and return head, now referencing the head of the list 3->2->1->Null. Function Descriptio