fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. using ld = long double;
  5. #define endme "\n";
  6. #define ffprint(x)        \
  7.     for (auto &i : x)      \
  8.     {                     \
  9.         cout << i << " "; \
  10.     } \
  11.     cout<<endme;
  12. #define vectinput(x) for(auto &i : x) cin >> i;
  13. #ifndef ONLINE_JUDGE
  14.    #include"Debug.cpp"
  15. #endif
  16.  
  17.  
  18. void dfs(int node,int parent,map<int,int>&mp,vector<vector<int>>&adj,vector<int>&values,int&answer,vector<int>&squarefree){
  19.     int sqaurefreepart=squarefree[values[node]];
  20.     if(mp.find(sqaurefreepart)!=mp.end()){
  21.         answer+=mp[sqaurefreepart];
  22.     }
  23.     mp[sqaurefreepart]++;
  24.     for(auto x:adj[node]){
  25.         if(x!=parent){
  26.             dfs(x,node,mp,adj,values,answer,squarefree);
  27.         }
  28.     }
  29.     mp[sqaurefreepart]--;
  30.     if(mp[sqaurefreepart]==0)mp.erase(sqaurefreepart);
  31. }
  32.  
  33.  
  34. void sieve(vector<bool>&primes,vector<int>&squarefree){
  35.     for(int i=1;i<squarefree.size();i++){
  36.         squarefree[i]=i;
  37.     }
  38.     primes[0]=primes[1]=false;
  39.     for(int i=2;i<squarefree.size();i++){
  40.         if(!primes[i])continue;
  41.         for(int j=i*i;j<squarefree.size();j+=i){
  42.             primes[j]=false;
  43.             while((squarefree[j]%(i*i)==0)){
  44.                 squarefree[j]/=(i*i);
  45.             }
  46.         }
  47.     }
  48.     // debug(squarefree);
  49. }
  50.  
  51. void solve(){
  52.     int n;
  53.     cin>>n;
  54.     vector<vector<int>> adj(n);
  55.     vector<int>values(n);
  56.     vectinput(values);
  57.     for(int i=0;i<n-1;i++){
  58.         int a,b;
  59.         cin>>a>>b;
  60.         adj[a].push_back(b);
  61.         adj[b].push_back(a);
  62.     }
  63.  
  64.     int answer=0;
  65.     int mx=*max_element(values.begin(),values.end());
  66.     vector<bool>primes(mx+2,true);
  67.     vector<int>squarefree(mx+2);
  68.  
  69.     sieve(primes,squarefree);
  70.  
  71.     map<int,int> mp;
  72.     dfs(0,-1,mp,adj,values,answer,squarefree);
  73.     cout<<answer<<endme;
  74. }
  75.  
  76.  
  77. int main() {
  78.     ios::sync_with_stdio(false);
  79.     cin.tie(0);
  80.     cout.tie(0);
  81.     #ifndef ONLINE_JUDGE
  82.         freopen("0-InputFile/input.txt", "r", stdin);
  83.         freopen("0-InputFile/output.txt", "w", stdout);
  84.     #endif
  85.  
  86.    int t;
  87.    cin>>t;
  88. //    t=1;
  89.     while (t--) {
  90.         solve();
  91.     }
  92.     return 0;
  93. }
  94.  
  95. /*
  96. reset_template.bat
  97. %%%%%%%%+++*%@@@@@%%@%%%%%%%%%%%@@%%%%%%##**###%%%
  98. %%%%%%%%#*#%@@@@@@@%%%%%#%%%@@@@@%####**####%%@@@@
  99. %%%%%%%%##%@@@@@@@*+++++++++*#@@@@%####%%%%@@@@@@@
  100. %%%%%%%%#%%@@@@@#++++++++++++@@@@@@@%%%@@@@@@@@@@@
  101. @%#%%#%#%%%%%%*++++++++++++++*@@@@@@#++++++*######
  102. %%%%%#%%%###++++++++++++++++++*#@@@#*******#******
  103. #%%%%%%%%%%*+++++******+++++++++**++*##**+++***##%
  104. %%#%%%%%@@*++++*%@@#*****#%#*++++++++++++**##%@@@%
  105. %%%%%%%%%#+***#@@@#++*++*@@@#***+++++++*#%@@%##%%%
  106. %%%%%%%%#**###%@@#+++++++#@@@#*#**++**##%#####%@@@
  107. %%%%%%%%%**####%#++*##*++*@@@%###***#@@@@@%%%%@@@@
  108. %%%%%%%%%#*#####**#@@@@@***%%%%%##*%@@@@@@@@%%@@%%
  109. %%%%%%%%#%**######%%@@%##%%%%%%%##%@@@@@@@@@%#****
  110. %@@%%%###@@%#%%%@%%@@@@@@@%%%%%%%@@@@@@@@@@@@%#**#
  111. %%%%%%%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@###
  112. %%%#%%%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
  113. %%%%%%%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%
  114. %%%%%%%%%@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@%
  115. */
  116.  
  117.  
  118.  
  119.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
1
3
2 8 18
0 1
1 2
stdout
copy 
3
https://ideone.com/wsm9CT
language:
C++ (gcc 8.3)
created:
2 days 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!