fork download
copy 
  1. import java.util.HashSet;
  2. import java.util.LinkedList;
  3. import java.util.Queue;
  4. import java.util.Scanner;
  5.  
  6. public class Main {
  7.     public static void main(String[] args) {
  8.  
  9.         Scanner scanner = new Scanner(System.in);
  10.         int n = scanner.nextInt();
  11.  
  12.         HashSet<Integer>[] G = new HashSet[n];
  13.  
  14.         for(int i = 0; i < n; i++) {
  15.             G[i] = new HashSet<Integer>();
  16.         }
  17.  
  18.         int[] from = new int[n];
  19.         int[] to = new int[n];
  20.  
  21.         for(int i = 0; i < n - 1; i++) {
  22.             from[i] = scanner.nextInt();
  23.         }
  24.  
  25.         for(int i = 0; i < n - 1; i++) {
  26.             to[i] = scanner.nextInt();
  27.         }
  28.  
  29.         for(int i = 0; i < n - 1; i++) {
  30.            int u = from[i];
  31.            int v = to[i];
  32.            G[u].add(v);
  33.            G[v].add(u);
  34.         }
  35.  
  36.         int[] val = new int[n];
  37.  
  38.         for(int i = 0; i < n; i++) {
  39.             val[i] = scanner.nextInt();
  40.         }
  41.  
  42.         Queue<Integer> queue = new LinkedList<>();
  43.  
  44.         int destroyedNodes = 0;
  45.  
  46.         for(int i = 0; i < n; i++) {
  47.             if(G[i].size() == 1 && val[i] == 0) {
  48.                 queue.offer(i);
  49.             }
  50.         }
  51.  
  52.         while(!queue.isEmpty()) {
  53.  
  54.             int leafToDestroy = queue.poll();
  55.             int neighborOfLeafToDestroy = G[leafToDestroy].iterator().next();
  56.  
  57.             G[neighborOfLeafToDestroy].remove(leafToDestroy);
  58.             destroyedNodes++;
  59.  
  60.             if(G[neighborOfLeafToDestroy].size() == 1 && val[neighborOfLeafToDestroy] == 0) {
  61.                 queue.offer(neighborOfLeafToDestroy);
  62.             }
  63.         }
  64.  
  65.         System.out.println((n - destroyedNodes) << 1);
  66.     }
  67. }
Success #stdin #stdout 0.17s 56236KB
comments (?)
stdin
copy 
11
0 0 0 1 1 3 4 6 7 8
1 2 6 3 4 10 5 7 8 9
0 0 1 1 0 0 0 0 0 1 1
stdout
copy 
18
https://ideone.com/0FZCJg
language:
Java (HotSpot 12)
created:
1 day 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!