Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.*;
- import java.io.*;
- public class ClockTree {
- static int N;
- static int[] ct;
- static ArrayList<Integer>[] adj;
- static int[] numcons;
- static boolean fail = false;
- public static void dfs(int na, int[]ctcp, int[]nccy){
- if(fail)
- return;
- for (int nb: adj[na]){
- if (fail)
- return;
- if(ctcp[nb] >= 12 && nccy[na] ==1)
- {
- fail = true;
- return;
- }
- if (ctcp[nb] <12){
- ctcp[nb]++;
- dfs(nb,ctcp,nccy);
- }
- }
- }
- public static void main(String[] args) throws Exception{
- BufferedReader br= new BufferedReader (new InputStreamReader (System.in));
- StringTokenizer st = new StringTokenizer(br.readLine());
- N = Integer.parseInt(st.nextToken());
- ct = new int[N+1];
- st = new StringTokenizer (br.readLine());
- for(int i = 1; i <= N; ++i){
- ct[i] = Integer.parseInt(st.nextToken());
- }
- adj = new ArrayList[N+1];
- for(int i = 1; i <=N; ++i){
- ct[i] = Integer.parseInt(st.nextToken());
- }
- adj = new ArrayList[N+1];
- for(int i =1; i <=N; ++i)
- adj[i] = new ArrayList<Integer>();
- numcons = new int[N+1];
- for(int i = 1; i <= N-1; ++i){
- st = new StringTokenizer (br.readLine());
- int na = Integer.parseInt(st.nextToken());
- int nb = Integer.parseInt(st.nextToken());
- adj[na].add(nb);
- adj[nb].add(na);
- numcons[na]++;
- numcons[nb]++;
- }
- int cnt =0;
- for(int i =1; i <= N; ++i){
- int[] ctcp = ct.clone();
- int[] nccp = numcons.clone();
- fail = false;
- ArrayDeque<Integer> pq = new ArrayDeque<Integer>();
- pq.addLast(i);
- while(!fail && !pq.isEmpty()) {
- int na = pq.removeFirst();
- for(int nb: adj[na]) {
- if(fail)
- break;
- if(ctcp[nb] >= 12 && nccp[na] == 1) {
- fail =true;
- break;
- }
- if(ctcp[nb]<12) {
- ctcp[nb]++;
- pq.addLast(nb);
- break;
- }
- }
- }
- boolean isReach = true;
- for (int j=1; j<=N; ++j)
- if(ctcp[j] != 12)
- isReach = false;
- if(isReach)
- cnt++;
- }
- System.out.println(cnt);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement