fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define all(x) begin(x), end(x)
  6. #define int int64_t
  7.  
  8. const int maxn = 1e5 + 42;
  9. vector<int> g[maxn];
  10. int ans[maxn], val[maxn], mod[maxn];
  11.  
  12. void init() {
  13. 	for(int i = 0; i < maxn; i++) {
  14. 		g[i].clear();
  15. 		ans[i] = -1;
  16. 	}
  17. }
  18.  
  19. void dfs(int v = 1, int p = 1, int G = val[1]) {
  20. 	for(auto u: g[v]) {
  21. 		if(u != p) {
  22. 			dfs(u, v, __gcd(G, val[u]));
  23. 		}
  24. 	}
  25. 	if(g[v].size() == 1 && v != 1) {
  26. 		ans[v] = mod[v] - __gcd(mod[v], G);
  27. 	}
  28. }
  29.  
  30. void solve() {
  31. 	init();
  32. 	int n;
  33. 	cin >> n;
  34. 	for(int i = 1; i < n; i++) {
  35. 		int x, y;
  36. 		cin >> x >> y;
  37. 		g[x].push_back(y);
  38. 		g[y].push_back(x);
  39. 	}
  40. 	for(int i = 1; i <= n; i++) {
  41. 		cin >> val[i];
  42. 	}
  43. 	for(int i = 1; i <= n; i++) {
  44. 		cin >> mod[i];
  45. 	}
  46. 	dfs();
  47. 	for(int i = 1; i <= n; i++) {
  48. 		if(ans[i] != -1) {
  49. 			cout << ans[i] << " \n"[i == n];
  50. 		}
  51. 	}
  52. }
  53.  
  54. signed main() {
  55. 	//freopen("input.txt", "r", stdin);
  56. 	//freopen("output.txt", "w", stdout);
  57. 	ios::sync_with_stdio(0);
  58. 	cin.tie(0);
  59. 	int t;
  60. 	cin >> t;
  61. 	while(t--) {
  62. 		solve();
  63. 	}
  64. 	return 0;
  65. }
Success #stdin #stdout 0s 19928KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/IFYbS9
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!