Advertisement
Guest User

Untitled

a guest
Feb 24th, 2020
240
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.02 KB | None | 0 0
  1. import java.util.*;
  2. import java.io.*;
  3.  
  4. public class ClockTree {
  5. static int N;
  6. static int[] ct;
  7. static ArrayList<Integer>[] adj;
  8. static int[] numcons;
  9. static boolean fail = false;
  10.  
  11. public static void dfs(int na, int[]ctcp, int[]nccy){
  12. if(fail)
  13. return;
  14. for (int nb: adj[na]){
  15. if (fail)
  16. return;
  17. if(ctcp[nb] >= 12 && nccy[na] ==1)
  18. {
  19. fail = true;
  20. return;
  21. }
  22. if (ctcp[nb] <12){
  23. ctcp[nb]++;
  24. dfs(nb,ctcp,nccy);
  25. }
  26. }
  27. }
  28.  
  29. public static void main(String[] args) throws Exception{
  30. BufferedReader br= new BufferedReader (new InputStreamReader (System.in));
  31. StringTokenizer st = new StringTokenizer(br.readLine());
  32. N = Integer.parseInt(st.nextToken());
  33. ct = new int[N+1];
  34. st = new StringTokenizer (br.readLine());
  35.  
  36. for(int i = 1; i <= N; ++i){
  37. ct[i] = Integer.parseInt(st.nextToken());
  38. }
  39. adj = new ArrayList[N+1];
  40. for(int i = 1; i <=N; ++i){
  41. ct[i] = Integer.parseInt(st.nextToken());
  42. }
  43. adj = new ArrayList[N+1];
  44. for(int i =1; i <=N; ++i)
  45. adj[i] = new ArrayList<Integer>();
  46. numcons = new int[N+1];
  47. for(int i = 1; i <= N-1; ++i){
  48. st = new StringTokenizer (br.readLine());
  49. int na = Integer.parseInt(st.nextToken());
  50. int nb = Integer.parseInt(st.nextToken());
  51. adj[na].add(nb);
  52. adj[nb].add(na);
  53. numcons[na]++;
  54. numcons[nb]++;
  55. }
  56.  
  57. int cnt =0;
  58. for(int i =1; i <= N; ++i){
  59. int[] ctcp = ct.clone();
  60. int[] nccp = numcons.clone();
  61. fail = false;
  62. ArrayDeque<Integer> pq = new ArrayDeque<Integer>();
  63. pq.addLast(i);
  64. while(!fail && !pq.isEmpty()) {
  65. int na = pq.removeFirst();
  66. for(int nb: adj[na]) {
  67. if(fail)
  68. break;
  69. if(ctcp[nb] >= 12 && nccp[na] == 1) {
  70. fail =true;
  71. break;
  72. }
  73. if(ctcp[nb]<12) {
  74. ctcp[nb]++;
  75. pq.addLast(nb);
  76. break;
  77. }
  78. }
  79. }
  80.  
  81. boolean isReach = true;
  82. for (int j=1; j<=N; ++j)
  83. if(ctcp[j] != 12)
  84. isReach = false;
  85. if(isReach)
  86. cnt++;
  87. }
  88. System.out.println(cnt);
  89. }
  90. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement