fork download
copy 
  1. import java.util.*;
  2. class TreeDP {
  3.     static List<Integer>[] G;
  4.     static int[] nodeValue, parent, dp;
  5.  
  6.     public static void dfs(int node, int par) {
  7.         //1. dfs deeply
  8.         parent[node] = par;
  9.         for (int child : G[node]) {
  10.             if (child != par) {
  11.                 dfs(child, node);
  12.             }
  13.         }
  14.         // 2. take current number of buses so far as the buses that kids have 
  15.         // multiple children means those subtrees kids
  16.         // we can have multiple leaves
  17.         for (int u : G[node]) {
  18.             if (u != parent[node]) {
  19.                 dp[node] += dp[u];
  20.             }
  21.         }
  22.  
  23.         // basically this condition makes sure this node is a leaf
  24.         // we have previously marked for parent .. but if its a leaf node the dp[node] 
  25.         // would still be empty. Instead of checking for leaf node or not we can just mark
  26.         // dp of the parent as 2. this below cond would only happen for leaves
  27.         if (dp[node] == 0 && nodeValue[node] == 1) {
  28.             dp[node] = 1;
  29.         }
  30.     }
  31.  
  32.     public static void main(String[] args) {
  33.         Scanner sc = new Scanner(System.in);
  34.         int N = sc.nextInt();
  35.  
  36.         G = new ArrayList[N + 1];
  37.         nodeValue = new int[N + 1];
  38.         parent = new int[N + 1];
  39.         dp = new int[N + 1];
  40.  
  41.         for (int i = 1; i <= N; i++) {
  42.             G[i] = new ArrayList<>();
  43.             nodeValue[i] = sc.nextInt();
  44.         }
  45.  
  46.         for (int i = 1; i < N; i++) {
  47.             int u = sc.nextInt();
  48.             int v = sc.nextInt();
  49.             G[u].add(v);
  50.             G[v].add(u);
  51.         }
  52.  
  53.         dfs(1, -1); // Start DFS from root node 1
  54.  
  55.         System.out.println(dp[1]); // Output the minimum number of buses needed
  56.         sc.close();
  57.     }
  58. }
  59.  
Success #stdin #stdout 0.11s 56484KB
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/wVSCfA
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!