[Porblem](http://codeforces.net/contest/514/problem/E)
Hi guys,
I think the solution provided for this problem is wrong. I solved this problem in two ways. I have given my solutions below. Please correct me if I am wrong.
Approach-1(recursion)
-> Start with root
-> form child nodes if(distance<x) and call this method for all new nodes
--> count the no of nodes
-
**java code:**
****
import java.util.Arrays;
import java.util.Scanner;
public class maxtree {
static int count=1;
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int x=sc.nextInt();
int[] d=new int[n];
for(int i=0;i<n;i++){
d[i]=sc.nextInt();
}
Arrays.sort(d);
//System.out.println(n+x);
node n2=new node(0);
//n2.setDistance(0);
build(n2,x,d);
System.out.println(count);
}
public static void build(node n,int x,int[] d){
int di=n.getDistance();
if(di<x){
//System.out.println(di);
int dummy=x-di;
int len=d.length;
for(int i=0;i<len && dummy>=d[i];i++){
n=new node(di+d[i]);
//n.setDistance(di+d[i]);
count++;
//System.out.println(count);
build(n,x,d);
}
}
}
}
class node{
int distance=Integer.MAX_VALUE;
public node(int d){
distance=d;
}
public int getDistance() {
return distance;
}
public void setDistance(int distance) {
this.distance = distance;
}
}
**Second approach(DP):**
-> take all distinct di and sort them
- >Let the number of vertexes in the tree at distance from the root equal to at most x=no
- >no(0)=1;
- >no(1)=2 if di contains 1
- >for(x=n), this no will be
-> no(n-d1)+no(n-d2)+no(n-d3)+...........till n>=di
**Java code:**
import java.util.Arrays;
import java.util.Scanner;
public class maxtree1 {
//static int count=1;
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
int x=sc.nextInt();
int[] d=new int[n];
for(int i=0;i<n;i++){
d[i]=sc.nextInt();
}
Arrays.sort(d);
//System.out.println(n+x);
long[] table=new long[x];
if(d[0]==1){
table[0]=2;
}else{
table[0]=1;
}
int count=0;
for(int i=1;i<x;i++){
count=1;
for(int j=0;j<n && i+1>=d[j];j++){
if(i+1!=d[j]){
count+=table[i-d[j]];
}else{
count++;
}
table[i]=count;
}
System.out.println(table[i]);
}
}
}