fork download
copy 
  1. def read_graph(hm, edges):
  2.   for i in range(edges - 1):
  3.     u, v = map(int, input().split())
  4.     hm[u].append(v)
  5. def BFS(hm, s, c, a, noc):
  6.   cnt = 0
  7.   nc = 0
  8.   q = []
  9.   q.append(s)
  10.   while(len(q) != 0):
  11.     t = q.pop(0)
  12.     #print(t)
  13.     if(t == 1 and a[t-1] == 1):
  14.       noc[t] = 1
  15.  
  16.     if(len(hm[t]) == 0):
  17.       if(noc[t] <= c):
  18.         cnt += 1
  19.     else:
  20.       current = hm[t]
  21.       for i in range(len(hm[t])):
  22.  
  23.         #print(q)
  24.        # print(current[i])
  25.        # print(noc)
  26.         #print(a)
  27.         if(visited[current[i]] == 0):
  28.         	visited[current[i]] = 1
  29. 	        if(a[current[i] - 1] == 1):
  30. 	          noc[current[i]] = noc[t] + a[current[i] - 1]
  31. 	        #print(noc[current[i]])
  32. 	        #print(c)
  33. 	        if(noc[current[i]] > c):
  34. 	          continue
  35. 	        else:
  36. 	          q.append(current[i])
  37.         #print(q)
  38.   #print(noc)
  39.   return cnt
  40. n, m = map(int, input().split())
  41. a = list(map(int, input().split()))
  42.   #x,y = map(int, input().split())
  43. hm = []
  44. noc = []
  45. visited = []
  46.  
  47. for item in range(n + 1):
  48.   hm.append([])
  49.   noc.append(0)
  50.   visited.append(0)
  51. read_graph(hm, n)
  52. print(BFS(hm,1,m,a,noc))
  53.  
Success #stdin #stdout 0.02s 9164KB
comments (?)
stdin
copy 
7 1
1 0 1 1 0 0 0
1 2
1 3
2 4
2 5
3 6
3 7
stdout
copy 
2
https://ideone.com/HcI0y0
language:
Python 3 (python  3.9.5)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!