fork download
copy 
  1. import java.util.*;
  2. import java.io.*;
  3.  
  4. public class Main {
  5.     public static void main(String[] args) throws IOException {
  6.     	Scanner in = new Scanner(System.in);
  7.  
  8.         int n = in.nextInt();
  9.         int M = in.nextInt();
  10.  
  11.         int[] b = new int[n + 1];
  12.         for (int i = 1; i <= n; i++) {
  13.             b[i] = in.nextInt();
  14.         }
  15.  
  16.         ArrayList<Integer>[] G = new ArrayList[n + 1];
  17.         for (int i = 0; i <= n; i++) G[i] = new ArrayList<>();
  18.  
  19.         for (int i = 1; i <= n - 1; i++) {
  20.             int u = in.nextInt();
  21.             int v = in.nextInt();
  22.             G[u].add(v);
  23.             G[v].add(u);
  24.         }
  25.  
  26.         int[] prefix = new int[n + 1];
  27.         int[] used = new int[n + 1];
  28.         int[] maxi = new int[n + 1];
  29.  
  30.         Queue<Integer> q = new LinkedList<>();
  31.         q.add(1);
  32.         used[1] = 1;
  33.  
  34.         if (b[1] == 0) prefix[1] = 1;
  35.         maxi[1] = prefix[1];
  36.  
  37.         while (!q.isEmpty()) {
  38.             int v = q.poll();
  39.             System.out.println(v + " " + prefix[v]);
  40.             for (int child : G[v]) {
  41.                 if (used[child] == 0) {
  42.                     used[child] = 1;
  43.                     q.add(child);
  44.                     if (b[child] == 0) {
  45.                         prefix[child] = 1 + prefix[v];
  46.                         maxi[child] = Math.max(prefix[child], maxi[v]);
  47.                     }
  48.                 }
  49.             }
  50.         }
  51.  
  52.         // Check leaf nodes (except node 1)
  53.         int count = 0;
  54.         for (int i = 2; i <= n; i++) {
  55.             if (G[i].size() == 1 && maxi[i] <= M) {
  56.                 count++;
  57.             }
  58.         }
  59.  
  60.         System.out.println(count);
  61.     }
  62. }
  63.  
Success #stdin #stdout 0.23s 58828KB
comments (?)
stdin
copy 
5 3
1 0 0 1 0 
1 2
2 3
1 4 
4 5
stdout
copy 
1 0
2 1
4 0
3 2
5 1
2
https://ideone.com/FkMdt7
language:
Java (HotSpot 12)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!