?
# | 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 |
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(); } }
?
?
?
?