SHARE
TWEET

Untitled

a guest Jan 21st, 2019 48 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.io.*;
  2. import java.util.*;
  3. class Tuple {
  4.     public int a, b;
  5.     public Tuple(int a, int b) {
  6.         this.a=a;
  7.         this.b=b;
  8.     }
  9. }      
  10.  
  11. public class mootube {
  12.     public static int dfs(int v, int k, ArrayList<Tuple>[] matrix) {
  13.         int result = 0;
  14.         LinkedList<Integer> explore = new LinkedList<Integer>();
  15.         // Set<Integer> visited = new HashSet<Integer>();
  16.         boolean[] visited = new boolean[matrix.length];
  17.         explore.add(v);
  18.  
  19.         while (!explore.isEmpty()) {
  20.             int node = explore.remove();
  21.  
  22.             visited[node] = true;
  23.  
  24.             for (Tuple tup: matrix[node]) {
  25.                 int cost = tup.b;
  26.                 int u = tup.a;
  27.  
  28.                 if (!visited[u] && cost>=k) {
  29.                     explore.add(u);
  30.                     result += 1;
  31.                 }
  32.             }
  33.         }
  34.         return result;
  35.     }
  36.  
  37.     public static void main(String[] args) throws IOException {
  38.         BufferedReader f = new BufferedReader(new FileReader("mootube.in"));
  39.         PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("mootube.out")));
  40.         StringTokenizer st = new StringTokenizer(f.readLine());
  41.  
  42.         int n = Integer.parseInt(st.nextToken());
  43.         int q = Integer.parseInt(st.nextToken());
  44.  
  45.         ArrayList<Tuple>[] matrix = new ArrayList[n];
  46.  
  47.         for(int i = 0; i < n-1; i++) {
  48.             st = new StringTokenizer(f.readLine());
  49.             int a = Integer.parseInt(st.nextToken())-1;
  50.             int b = Integer.parseInt(st.nextToken())-1;
  51.             int cost = Integer.parseInt(st.nextToken());
  52.             if (matrix[a] == null) matrix[a] = new ArrayList<Tuple>();
  53.             if (matrix[b] == null) matrix[b] = new ArrayList<Tuple>();
  54.             matrix[a].add(new Tuple(b, cost));
  55.             matrix[b].add(new Tuple(a, cost));
  56.         }
  57.  
  58.         for(int j = 0; j < q; j++) {
  59.             st = new StringTokenizer(f.readLine());
  60.             int k = Integer.parseInt(st.nextToken());
  61.             int v = Integer.parseInt(st.nextToken())-1;
  62.             out.println(dfs(v, k, matrix));
  63.         }
  64.         out.close();
  65.         f.close();
  66.     }
  67. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top