fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define fast ios_base::sync_with_stdio(0),cin.tie(0);
  4. using namespace std;
  5. const ll N=1e5,M=1e6+5;
  6.  
  7. vector<ll> g[N+5];
  8.  
  9. map<ll,map<ll,ll>> d;
  10. ll st[N+5],timedfs=0,en[N+5],c[N+5],a[N+5];
  11.  
  12. void dfs(ll u,ll pre){
  13.     st[u]=++timedfs;
  14.    c[st[u]]=u;
  15.  
  16.  for(int v:g[u]){
  17.     if(v==pre) continue;
  18.     dfs(v,u);
  19.  }
  20.  en[u]=timedfs;
  21. }
  22. ll snt[N+5];
  23.  
  24. void ok(){
  25.   for(int i=1;i<=N;i++)
  26.     snt[i]=i;
  27.  
  28.   for(int i=2;i<=N;i++)
  29.    if(snt[i]==i)
  30.     for(int j=2*i;j<=N;j+=i)
  31.         if(snt[j]==j) snt[j]=i;
  32.  
  33. }
  34. ll siu[N+5];
  35.  
  36. int main(){
  37. fast
  38. ll n;
  39. cin>>n;
  40. for(int i=1;i<=n;i++)
  41.     cin>>a[i];
  42.  
  43. for(int i=1;i<n;i++){
  44.     ll u,v;
  45.     cin>>u>>v;
  46.     g[u].push_back(v);
  47.     g[v].push_back(u);
  48. }
  49.   dfs(1,0);
  50.  for(int i=1;i<=n;i++)
  51.     g[i].clear();
  52.  
  53.   set<ll> s;
  54.   ok();
  55.   for(int i=1;i<=n;i++){
  56.         s.clear();
  57.     ll u1=c[i];
  58.     ll u=a[u1];
  59.  
  60.     while(u>1){
  61.         s.insert(snt[u]);
  62.         u/=snt[u];
  63.     }
  64.     for(auto x:s)
  65.         g[u1].push_back(x);
  66.  
  67.   }
  68.  
  69. for(int i=1;i<=n;i++){
  70.   d[i]=d[i-1];
  71.   ll u=c[i];
  72.   ll m=g[u].size();
  73.   for(int mask=0;mask<(1<<m);mask++){
  74.       ll d1=1;
  75.     for(int j=0;j<m;j++)
  76.         if(mask>>j&1) d1*=g[u][j];
  77.      d[i][d1]++;
  78.   }
  79.  
  80. }
  81. for(int i=1;i<=n;i++){
  82.         ll u=c[i];
  83.     //cout<<u<<" ";
  84.     ll x=st[u],y=en[u];
  85.     ll m=g[u].size();
  86.     ll res=0;
  87.  
  88.   for(int mask=0;mask<(1<<m);mask++){
  89.       ll d1=1,cnt=0;
  90.     for(int j=0;j<m;j++)
  91.         if(mask>>j&1) d1*=g[u][j],cnt++;
  92.  
  93.        if(cnt%2==0) res+=d[y][d1]-d[x-1][d1];
  94.        else res-=d[y][d1]-d[x-1][d1];
  95.   }
  96.   siu[u]=res;
  97.  
  98. }
  99. for(int i=1;i<=n;i++)
  100.     cout<<siu[i]<<" ";
  101.  
  102. return 0;
  103. }
  104. /*
  105. 5
  106. 66 15 5 7 11
  107. 1 2
  108. 2 3
  109. 2 4
  110. 1 5
  111. */
  112.  
Success #stdin #stdout 0.01s 9872KB
comments (?)
stdin
copy 
5
66 15 5 7 11
1 2
3 2
2 4
1 5
stdout
copy 
2 1 0 0 0
https://ideone.com/QiMW8Z
language:
C++ (gcc 8.3)
created:
7 hours 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!