Coloring trees

There are $N$ cities that are connected by $N-1$ roads. $K$ cities have bus terminals and other $N-K$ cities have bus stops. A bus terminus is a designated place where a bus starts or ends its scheduled route.
A bus should start from a terminal and must end its journey at another terminal visiting any city at most once. A city is crowded if there is a bus service in the city where one or more than one bus visits it along any route. You are required to simulate the routes for the buses so that the maximum number of cities is crowded. You can assume there is a number of buses ready for service from each terminus.

Input 

5 3
1 2
1 3
2 4
2 5
1 4 5

Output

4

Solution


import java.util.*;



class TestClass {

public static int ans=0;

public static void main(String args[] ) throws Exception {

Scanner s = new Scanner(System.in);

int n=s.nextInt();

int k=s.nextInt();

int u=0;

LinkedList<Integer> l[]=new LinkedList[n+1];

boolean b[]=new boolean[n+1];

int ter[]=new int[n+1];

int con[]=new int[n+1];

for (int i = 1; i <n+1; i++)

{        b[i]=false;

ter[i]=0;

l[i] = new LinkedList<Integer>();

}

for (int i = 0; i < n-1; i++)

{

u=s.nextInt();

int v=s.nextInt();

l[u].add(v);

l[v].add(u);

}

int te=0;

for(int i=1;i<=k;i++)

{te=s.nextInt();

ter[te]=1;

con[te]=1;

}



dfs(te,b,ter,l,con);

for(int i=1;i<n+1;i++){

if(con[i]==1)

ans++;

} 

System.out.println(ans);

}

public static boolean dfs(int src,boolean b[],int ter[],LinkedList l[],int con[]){

b[src]=true;

boolean f=false;

if(ter[src]==1)

{

f=true;

}

int y;

Iterator<Integer> it=l[src].iterator();

while(it.hasNext())

{ y=it.next();

if(!b[y]){

if( dfs(y,b,ter,l,con))

{

con[src]=1;

f=true;

}

}

}

return f; 

}


}





if you have any problem in this code, take a screen shot and contact with Rishabh Chaubey.