General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
52615031 Practice:
kukreja-vlk
580C - 7 Java 8 Accepted 311 ms 47496 KB 2019-04-11 20:57:57 2019-04-11 20:57:57
→ Source
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.*;

public class Codeforces {

    static int MAX = -1 >>> 1;
    static long MOD = 1_000_000_007L;

    static class Graph {
        int n;
        List<Integer>[] adj;
        int[] a;
        Graph(int[] a, int n) {
            this.n = n;
            this.a = a;
            this.adj = new List[1 + n];
            for(int i = 1; i <= n; i++) {
                this.adj[i] = new ArrayList<Integer>();
            }
        }
        void addEdge(int u, int v) {
            adj[u].add(v);
            adj[v].add(u);
        }
        int bfs(boolean[] visited, int src, int m, int om) {
            // println("src = " + src + ", m = " + m);
            if(m < 0) return 0;
            visited[src] = true;
            int ans = 0;
            boolean childFound = false;
            for(int nei : adj[src]) {
                if(visited[nei]) continue;
                childFound = true;
                ans += a[src - 1] == 1 ? bfs(visited, nei, m - 1, om) : bfs(visited, nei, om, om);
            }
            if(!childFound) {
                //leaf kitchen
                if(a[src - 1] == 1 && m == 0) {
                    ans = 0;
                    // println("found kitchen at " + src + " but it has cats and we are out of patience!");
                }
                else ans = 1;       
            }
            return ans;
        }
    }
    
    static void main2() throws Exception {
        int n = ni();
        int m = ni();
        int[] a = nia(n);
        Graph g = new Graph(a, n);
        for(int i = 0; i < n - 1; i++) {
            int u = ni();
            int v = ni();
            g.addEdge(u, v);
        }
        // println(Arrays.toString(g.adj));
        int ans = g.bfs(new boolean[1 + n], 1, m, m);
        println(ans);        

    }
    //            /$$
    //           | $$
    //   /$$$$$$$| $$  /$$$$$$   /$$$$$$$ /$$$$$$$  /$$$$$$   /$$$$$$$
    //  /$$_____/| $$ |____  $$ /$$_____//$$_____/ /$$__  $$ /$$_____/
    // | $$      | $$  /$$$$$$$|  $$$$$$|  $$$$$$ | $$$$$$$$|  $$$$$$
    // | $$      | $$ /$$__  $$ \____  $$\____  $$| $$_____/ \____  $$
    // |  $$$$$$$| $$|  $$$$$$$ /$$$$$$$//$$$$$$$/|  $$$$$$$ /$$$$$$$/
    //  \_______/|__/ \_______/|_______/|_______/  \_______/|_______/

    static class Pair <L, R> {
        L first;
        R second;

        Pair(L first, R second) {
            this.first = first;
            this.second = second;
        }

        Pair(Pair<L, R> p) {
            this.first = p.first;
            this.second = p.second;
        }

        public boolean equals(Object p2) {
            if (p2 instanceof Pair) {
                return ((Pair) p2).first.equals(first) && ((Pair) p2).second.equals(second);
            }
            return false;
        }

        public String toString() {
            return "(first=" + first.toString() + ",second=" + second.toString() + ")";
        }
    }

    static class DisjointSet {
        int[] arr;
        int[] size;
        boolean enableSize = false;

        DisjointSet(int n, boolean enableSize) {
            arr = new int[n + 1];
            this.enableSize = enableSize;
            if(this.enableSize) size = new int[n + 1];
            makeSet();
        }

        void makeSet() {
            for (int i = 1; i < arr.length; i++) {
                arr[i] = i;
                if(enableSize) size[i] = 1;
            }
        }

        void union(int i, int j) {
            if (i == j)
                return;
            if (i > j) {
                i ^= j;
                j ^= i;
                i ^= j;
            }

            i = find(i);
            j = find(j);

            if (i == j)
                return;
            arr[j] = arr[i];
            if(enableSize) {
                size[i] += size[j];
                size[j] = size[i];
            }
        }

        int find(int i) {
            if (arr[i] != i) {
                arr[i] = find(arr[i]);
                if(enableSize) size[i] = size[arr[i]];
            }
            return arr[i];
        }

        int getSize(int i) {
           i = find(i);
           if(enableSize) return size[i];
           return 0;
        }

        public String toString() {
            return Arrays.toString(arr);
        }
    }

    //              /$$     /$$ /$$
    //             | $$    |__/| $$
    //  /$$   /$$ /$$$$$$   /$$| $$  /$$$$$$$
    // | $$  | $$|_  $$_/  | $$| $$ /$$_____/
    // | $$  | $$  | $$    | $$| $$|  $$$$$$
    // | $$  | $$  | $$ /$$| $$| $$ \____  $$
    // |  $$$$$$/  |  $$$$/| $$| $$ /$$$$$$$/
    //  \______/    \___/  |__/|__/|_______/


    static int diff(int a, int b) {
        return abs(a - b);
    }

    static long diff(long a, long b) {
        return abs(a - b);
    }

    static boolean isSqrt(double a) {
        double sr = Math.sqrt(a);
        return ((sr - Math.floor(sr)) == 0);
    }

    static long abs(long a) {
        return Math.abs(a);
    }

    static int abs(int a) {
        return Math.abs(a);
    }

    static int min(int ... arr) {
        int min = Integer.MAX_VALUE;
        for (int var : arr)
            min = Math.min(min, var);
        return min;
    }

    static long min(long ... arr) {
        long min = Long.MAX_VALUE;
        for (long var : arr)
            min = Math.min(min, var);
        return min;
    }

    static long max(long ... arr) {
        long max = Long.MIN_VALUE;
        for (long var : arr)
            max = Math.max(max, var);
        return max;
    }

    static int max(int... arr) {
        int max = Integer.MIN_VALUE;
        for (int var : arr)
            max = Math.max(max, var);
        return max;
    }

    static long gcd(long a, long b) {
        if (b == 0)
            return a;
        return gcd(b, a % b);
    }

    // ____________________________________________________________________________
    //|                                                                            |
    //|  /$$$$$$  /$$$$$$         /$$$$$$   /$$                /$$$$$$   /$$$$$$   |
    //| |_  $$_/ /$$__  $$       /$$__  $$ | $$               /$$__  $$ /$$__  $$  |
    //|   | $$  | $$  \ $$      | $$  \__//$$$$$$   /$$   /$$| $$  \__/| $$  \__/  |
    //|   | $$  | $$  | $$      |  $$$$$$|_  $$_/  | $$  | $$| $$$$    | $$$$      |
    //|   | $$  | $$  | $$       \____  $$ | $$    | $$  | $$| $$_/    | $$_/      |
    //|   | $$  | $$  | $$       /$$  \ $$ | $$ /$$| $$  | $$| $$      | $$        |
    //|  /$$$$$$|  $$$$$$/      |  $$$$$$/ |  $$$$/|  $$$$$$/| $$      | $$        |
    //| |______/ \______/        \______/   \___/   \______/ |__/      |__/        |
    //|____________________________________________________________________________|



    private static byte[] scannerByteBuffer = new byte[1024]; // Buffer of Bytes
    private static int scannerIndex;
    private static InputStream scannerIn;
    private static int scannerTotal;
    private static BufferedWriter printerBW;
    private static boolean DEBUG = false;

    private static int next() throws IOException { // Scan method used to scan buf
        if (scannerTotal < 0)
            throw new InputMismatchException();
        if (scannerIndex >= scannerTotal) {
            scannerIndex = 0;
            scannerTotal = scannerIn.read(scannerByteBuffer);
            if (scannerTotal <= 0)
                return -1;
        }
        return scannerByteBuffer[scannerIndex++];
    }

    static int ni() throws IOException {
        int integer = 0;
        int n = next();
        while (isWhiteSpace(n)) // Removing startPointing whitespaces
            n = next();
        int neg = 1;
        if (n == '-') { // If Negative Sign encounters
            neg = -1;
            n = next();
        }
        while (!isWhiteSpace(n)) {
            if (n >= '0' && n <= '9') {
                integer *= 10;
                integer += n - '0';
                n = next();
            } else
                throw new InputMismatchException();
        }
        return neg * integer;
    }

    static long nl() throws IOException {
        long integer = 0;
        int n = next();
        while (isWhiteSpace(n)) // Removing startPointing whitespaces
            n = next();
        int neg = 1;
        if (n == '-') { // If Negative Sign encounters
            neg = -1;
            n = next();
        }
        while (!isWhiteSpace(n)) {
            if (n >= '0' && n <= '9') {
                integer *= 10;
                integer += n - '0';
                n = next();
            } else
                throw new InputMismatchException();
        }
        return neg * integer;
    }

    static String line() throws IOException {
        StringBuilder sb = new StringBuilder();
        int n = next();
        while (isWhiteSpace(n))
            n = next();
        while (!isNewLine(n)) {
            sb.append((char) n);
            n = next();
        }
        return sb.toString();
    }

    private static boolean isNewLine(int n) {
        return n == '\n' || n == '\r' || n == -1;
    }

    private static boolean isWhiteSpace(int n) {
        return n == ' ' || isNewLine(n) || n == '\t';
    }

    static int[] nia(int n) throws Exception {
        if (n < 0)
            throw new Exception("Array size should be non negative");
        int[] array = new int[n];
        for (int i = 0; i < n; i++)
            array[i] = ni();
        return array;
    }

    static int[][] n2dia(int r, int c) throws Exception {
        if (r < 0 || c < 0)
            throw new Exception("Array size should be non negative");
        int[][] array = new int[r][c];
        for (int i = 0; i < r; i++)
            array[i] = nia(c);
        return array;
    }

    static long[] nla(int n) throws Exception {
        if (n < 0)
            throw new Exception("Array size should be non negative");
        long[] array = new long[n];
        for (int i = 0; i < n; i++)
            array[i] = nl();
        return array;
    }

    static float[] nfa(int n) throws Exception {
        if (n < 0)
            throw new Exception("Array size should be non negative");
        float[] array = new float[n];
        for (int i = 0; i < n; i++)
            array[i] = nl();
        return array;
    }

    static double[] nda(int n) throws Exception {
        if (n < 0)
            throw new Exception("Array size should be non negative");
        double[] array = new double[n];
        for (int i = 0; i < n; i++)
            array[i] = nl();
        return array;
    }

    static <T> void print(T ... str) {
        try {
            for (T ele : str)
                printerBW.append(ele.toString());
            if (DEBUG)
                flush();
        } catch (IOException e) {
            System.out.println(e.toString());
        }
    }

    static <T> void println(T ... str) {
        if (str.length == 0) {
            print('\n');
            return;
        }
        for (T ele : str)
            print(ele, '\n');
    }

    static void flush() throws IOException {
        printerBW.flush();
    }

    static void close() {
        try {
            printerBW.close();
        } catch (IOException e) {
            System.out.println(e.toString());
        }
    }

    public static void main(String[] args) throws Exception {
        long startPointTime = System.currentTimeMillis();
        scannerIn = System.in;
        printerBW = new BufferedWriter(new OutputStreamWriter(System.out));
        if (args.length > 0 && args[0].equalsIgnoreCase("debug")
                || args.length > 1 && args[1].equalsIgnoreCase("debug"))
            DEBUG = true;

        main2();
        long endTime = System.currentTimeMillis();
        float totalProgramTime = endTime - startPointTime;
        if (args.length > 0 && args[0].equalsIgnoreCase("time") || args.length > 1 && args[1].equalsIgnoreCase("time"))
            print("Execution time is " + totalProgramTime + " (" + (totalProgramTime / 1000) + "s)");
        close();
    }
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details