fork download
copy 
  1. import java.util.*;
  2. class TreeLeaves {
  3.  
  4.     static List<Integer>[] G;
  5.     static int[] nodeValue;
  6.     static int count = 0;
  7.  
  8.     static void dfs(int node, int parent) {
  9.  
  10.         boolean isLeaf = true;
  11.  
  12.         for (int child : G[node]) {
  13.             if (child != parent) {
  14.                 isLeaf = false;
  15.                 dfs(child, node);
  16.             }
  17.         }
  18.  
  19.         // Count only leaves whose value is 1
  20.         if (isLeaf && nodeValue[node] == 1) {
  21.             count++;
  22.         }
  23.     }
  24.  
  25.     public static void main(String[] args) {
  26.  
  27.         Scanner sc = new Scanner(System.in);
  28.  
  29.         int N = sc.nextInt();
  30.  
  31.         G = new ArrayList[N + 1];
  32.         nodeValue = new int[N + 1];
  33.  
  34.         // Initialize graph
  35.         for (int i = 1; i <= N; i++) {
  36.             G[i] = new ArrayList<>();
  37.         }
  38.  
  39.         // Node values
  40.         for (int i = 1; i <= N; i++) {
  41.             nodeValue[i] = sc.nextInt();
  42.         }
  43.  
  44.         // Edges
  45.         for (int i = 0; i < N - 1; i++) {
  46.             int u = sc.nextInt();
  47.             int v = sc.nextInt();
  48.  
  49.             G[u].add(v);
  50.             G[v].add(u);
  51.         }
  52.  
  53.         // Root the tree at node 1
  54.         dfs(1, -1);
  55.  
  56.         System.out.println(count);
  57.  
  58.         sc.close();
  59.     }
  60. }
Success #stdin #stdout 0.11s 56420KB
comments (?)
stdin
copy 
8
1 1 0 0 1 0 0 1
1 2
1 3
2 4
2 5
3 6
6 7
7 8
stdout
copy 
2
https://ideone.com/6nc8se
language:
Java (HotSpot 12)
created:
3 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!