fork download
copy 
  1. #include<bits/stdc++.h> /* SURAJ PRAKASH NARAYAN, CSE, MNNIT Alld, ad-astra */
  2. using namespace std;
  3.  
  4. #include <ext/pb_ds/assoc_container.hpp> // Common file
  5. #include <ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
  6. using namespace __gnu_pbds;
  7.  
  8. #define fast ios_base::sync_with_stdio(0); cin.tie(0);
  9. #define deb1(x) cout<<#x<<" :: "<<x<<"\n";
  10. #define deb2(x,y) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\n";
  11. #define deb3(x,y,z) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<"\n";
  12. #define trace(a) cout<<#a<<"\n";
  13.  
  14.  
  15. #define mp make_pair
  16. #define pb push_back
  17. #define F first
  18. #define S second
  19. #define ll long long
  20. #define dd double
  21. #define beg(a) a.begin(),a.end()
  22.  
  23. #define forr(a,b,n) for(int a=b;a<=n;++a)
  24. #define pll pair<ll,ll>
  25. #define vi std::vector<int>
  26. #define vll vector<ll>
  27. #define vp vector<pll>
  28.  
  29. #define mii std::map<int,int>
  30. #define mll std::map<ll,ll>
  31.  
  32.  
  33. #define si set<int>
  34. #define sll set<ll>
  35. #define sp set<pll>
  36.  
  37. #define ms0(arr) memset(arr,0,sizeof(arr));
  38. #define ms1(arr) memset(arr,1,sizeof(arr));
  39. #define ms_1(arr) memset(arr,-1,sizeof(arr));
  40. #define sz(a) a.size()
  41.  
  42. typedef tree<
  43. pll,
  44. null_type,
  45. less<pll>,
  46. rb_tree_tag,
  47. tree_order_statistics_node_update>
  48. ordered_set;
  49. //S.order_of_key(pii(sum - t, 1e9));
  50.  
  51. const int N = 1e6+5;
  52. const ll  MOD  = 998244353;
  53. const double eps = 1e-6;
  54. //............................................................................................................
  55. int values[200005];
  56. int maxl,ans;
  57. std::vector<int> adj[200005];
  58.  
  59. int dfs(int v,int p,int gcd){
  60. 	int maxx = 0,smax = 0;
  61. 	int a = __gcd(gcd,values[v]);
  62.  
  63. 	for(auto it:adj[v]){
  64. 		int len=0;
  65. 		if(it!=p)
  66. 			 len = dfs(it,v,(a>1)?a:values[v]);
  67. 		if(len>=maxx){
  68. 			smax = maxx,maxx=len;
  69. 		}
  70. 	}
  71. 	if(maxx>0){
  72. 		ans = max(ans,maxx+smax+1);
  73. 		return (a>1)?maxx+1:0;
  74. 	}else if(values[v]>1){
  75. 		ans = max(ans,1);
  76. 		return (a>1)?1:0;
  77. 	}else if(values[v]==1){
  78. 		return 0;
  79. 	}
  80.  
  81.  
  82. }
  83.  
  84. int main(int argc, char const *argv[])
  85. {	fast
  86. 	int n;
  87. 	cin>>n;
  88. 	for(int i=1;i<=n;++i){
  89. 		cin>>values[i];
  90. 	}
  91. 	for(int i=0;i<n-1;++i){
  92. 		int a,b;
  93. 		cin>>a>>b;
  94. 		adj[a].pb(b);
  95. 		adj[b].pb(a);
  96. 	}
  97.  
  98. 			dfs(1,1,0);
  99.  
  100. 	cout<<ans;
  101.  
  102. }
  103.  
  104.  
  105.  
  106.  
  107.  
  108.  
  109.  
  110.  
  111.  
  112.  
Success #stdin #stdout 0s 20704KB
comments (?)
stdin
copy 
7
2 4 8 5 10 15 20
1 2
2 3
2 4
4 6
4 5
6 7
stdout
copy 
3
https://ideone.com/9RCqNT
language:
C++14 (gcc 8.3)
created:
5 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!