# MATOM_t_py

Feb 22nd, 2021
75
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. import sys
2.
3. maxN = 3 * 100100
4. sys.setrecursionlimit(3 * 100100)
5.
6. def fast_input():
8.
9.
10. is_prime = [True for i in range(1000100)]
11. prime_less = [i for i in range(1000100)]
12.
13. is_prime[0] = is_prime[1] = False
14.
15. for i in range(2, int(1000100**0.5) + 1):
16.     if is_prime[i]:
17.         for j in range(i*i,1000100,i):
18.             is_prime[j] = False
19.
20.
21. for i in range(2, 1000100):
22.     prime_less[i] = prime_less[i-1]
23.     if is_prime[i]:
24.         prime_less[i] = i;
25.
26. n = int(fast_input())
27. adj = [[] for i in range(n + 1)]
28. final_score = [0 for i in range(n + 1)]
29. initial_score = [0]
30. transition_score = [0 for i in range(n + 1)]
31. final_node = [i for i in range(n + 1)]
32.
33. def dfs(node, par):
34.     min_score = final_score[node]
35.     curr_node = node
36.
38.         if child != par:
39.             dfs(child, node)
40.             if final_score[child] < min_score :
41.                 min_score = final_score[child]
42.                 curr_node = final_node[child]
43.
44.             elif final_score[child] == min_score:
45.                 if curr_node > final_node[child]:
46.                     curr_node = final_node[child]
47.
48.
49.     final_node[node] = curr_node
50.     final_score[node] = min_score
51.
52. initial_score = initial_score + list(map(int,fast_input().split()))
53.
54. assert len(initial_score) == n + 1
55.
56. for i in range(1, n + 1):
57.     transition_score[i] = prime_less[initial_score[i]]
58.     final_score[i] = transition_score[i]
59.
60.
61. for i in range(1,n):
62.     u,v = list(map(int,fast_input().split()))
65.
66.
67. dfs(1, 1)
68.
69. for i in range(1, n + 1):
70.     print(final_node[i], initial_score[i] - final_score[i])
71.
72.
RAW Paste Data