fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. const int MAXC = 10000000;
  6.  
  7. int N, Q;
  8. vector<int> cval;
  9. vector<vector<int>> g;
  10.  
  11. vector<int> euler;
  12. vector<int> inT, outT;
  13. int timerT = 0;
  14.  
  15. int LOGN = 17;
  16. vector<vector<int>> up;
  17. vector<int> depthv;
  18.  
  19. void dfs(int u, int p){
  20.     up[u][0] = p<0?u:p;
  21.     for(int k=1;k<LOGN;k++) up[u][k] = up[ up[u][k-1] ][k-1];
  22.     inT[u] = timerT;
  23.     euler[timerT++] = u;
  24.     for(int v: g[u]) if(v!=p){
  25.         depthv[v]=depthv[u]+1;
  26.         dfs(v,u);
  27.     }
  28.     outT[u] = timerT;
  29.     euler[timerT++] = u;
  30. }
  31.  
  32. int lca(int a, int b){
  33.     if(depthv[a]<depthv[b]) swap(a,b);
  34.     int diff = depthv[a]-depthv[b];
  35.     for(int k=0;k<LOGN;k++) if(diff&(1<<k)) a = up[a][k];
  36.     if(a==b) return a;
  37.     for(int k=LOGN-1;k>=0;k--) if(up[a][k]!=up[b][k]){ a=up[a][k]; b=up[b][k]; }
  38.     return up[a][0];
  39. }
  40.  
  41. inline long long hilbertOrder(int x, int y, int pow, int rot) {
  42.     if (pow == 0) return 0;
  43.     int hpow = 1 << (pow-1);
  44.     int seg = ( (x < hpow) ? ( (y < hpow) ? 0 : 3 ) : ( (y < hpow) ? 1 : 2 ) );
  45.     seg = (seg + rot) & 3;
  46.     static const int rotateDelta[4] = {3, 0, 0, 1};
  47.     int nx = x & (hpow-1), ny = y & (hpow-1);
  48.     int nrot = (rot + rotateDelta[seg]) & 3;
  49.     long long subSquareSize = 1LL << (2*pow - 2);
  50.     long long ord = seg * subSquareSize;
  51.     long long add = hilbertOrder(nx, ny, pow-1, nrot);
  52.     ord += (seg == 1 || seg == 2) ? add : (subSquareSize - add - 1);
  53.     return ord;
  54. }
  55.  
  56. struct Query{
  57.     int l, r, lca, id;
  58.     long long ord;
  59.     bool operator<(Query const& o) const{
  60.         return ord < o.ord;
  61.     }
  62. };
  63.  
  64. static int *spf_ptr = nullptr;
  65. static signed char *mu_ptr = nullptr;
  66.  
  67. void linear_sieve_and_mobius(int maxv){
  68.     int n = maxv;
  69.     int *spf = new int[n+1];
  70.     signed char *mu = new signed char[n+1];
  71.     vector<int> primes;
  72.     mu[0] = 0; mu[1] = 1; spf[0]=0; spf[1]=1;
  73.     for(int i=2;i<=n;i++) spf[i]=0;
  74.     for(int i=2;i<=n;i++){
  75.         if(!spf[i]){ spf[i]=i; primes.push_back(i); mu[i] = -1; }
  76.         for(int p: primes){
  77.             ll v = 1LL*p*i; if(v>n) break;
  78.             spf[v] = p;
  79.             if(i % p == 0){ mu[v] = 0; break; }
  80.             else mu[v] = -mu[i];
  81.         }
  82.     }
  83.     spf_ptr = spf;
  84.     mu_ptr = mu;
  85. }
  86.  
  87. inline int spf(int x){ return spf_ptr[x]; }
  88. inline signed char mu(int x){ return mu_ptr[x]; }
  89.  
  90. vector<vector<int>> sqfree_divs;
  91.  
  92. void gen_sqfree_divs_for_all(){
  93.     sqfree_divs.assign(N, {});
  94.     for(int i=0;i<N;i++){
  95.         int x = cval[i];
  96.         vector<int> primes;
  97.         while(x>1){
  98.             int p = spf(x);
  99.             primes.push_back(p);
  100.             while(x%p==0) x/=p;
  101.         }
  102.         int m = primes.size();
  103.         int subsets = 1<<m;
  104.         sqfree_divs[i].reserve(subsets);
  105.         for(int mask=1; mask<subsets; ++mask){
  106.             ll prod = 1;
  107.             for(int j=0;j<m;j++) if(mask&(1<<j)) prod *= primes[j];
  108.             if(prod <= MAXC) sqfree_divs[i].push_back((int)prod);
  109.         }
  110.         sqfree_divs[i].push_back(1);
  111.     }
  112. }
  113.  
  114. static int *cntDiv = nullptr;
  115.  
  116. vector<char> active;
  117. ll currentPairs = 0;
  118. int activeCount = 0;
  119.  
  120. inline void add_node(int node){
  121.     if(!active[node]){
  122.         ll cop = 0;
  123.         for(int d: sqfree_divs[node]){
  124.             cop += (ll) mu(d) * (ll) cntDiv[d];
  125.         }
  126.         currentPairs += cop;
  127.         for(int d: sqfree_divs[node]) cntDiv[d]++;
  128.         active[node]=1;
  129.         activeCount++;
  130.     } else {
  131.         for(int d: sqfree_divs[node]) cntDiv[d]--;
  132.         ll cop = 0;
  133.         for(int d: sqfree_divs[node]){
  134.             cop += (ll) mu(d) * (ll) cntDiv[d];
  135.         }
  136.         currentPairs -= cop;
  137.         active[node]=0;
  138.         activeCount--;
  139.     }
  140. }
  141.  
  142. int main(){
  143.     ios::sync_with_stdio(false);
  144.     cin.tie(nullptr);
  145.  
  146.     cin >> N >> Q;
  147.     cval.assign(N,0);
  148.     int maxc = 1;
  149.     for(int i=0;i<N;i++){ cin >> cval[i]; maxc = max(maxc, cval[i]); }
  150.     g.assign(N,{});
  151.     for(int i=0;i<N-1;i++){ int u,v; cin>>u>>v; --u;--v; g[u].push_back(v); g[v].push_back(u); }
  152.  
  153.     linear_sieve_and_mobius(maxc);
  154.  
  155.     inT.assign(N,0); outT.assign(N,0);
  156.     euler.assign(2*N, -1);
  157.     timerT=0;
  158.     LOGN = 1;
  159.     while((1<<LOGN) <= N) LOGN++;
  160.     up.assign(N, vector<int>(LOGN));
  161.     depthv.assign(N,0);
  162.     dfs(0,-1);
  163.  
  164.     gen_sqfree_divs_for_all();
  165.  
  166.     cntDiv = (int*)calloc((maxc+1), sizeof(int));
  167.  
  168.     vector<Query> queries; queries.reserve(Q);
  169.     int H = 0;
  170.     while((1<<H) < 2*N) H++;
  171.     for(int i=0;i<Q;i++){
  172.         int u,v; cin>>u>>v; --u; --v;
  173.         if(inT[u] > inT[v]) swap(u,v);
  174.         int w = lca(u,v);
  175.         Query qu;
  176.         qu.id = i;
  177.         if(w==u){
  178.             qu.l = inT[u]; qu.r = inT[v]; qu.lca = -1;
  179.         } else {
  180.             qu.l = outT[u]; qu.r = inT[v]; qu.lca = w;
  181.         }
  182.         qu.ord = hilbertOrder(qu.l, qu.r, H, 0);
  183.         queries.push_back(qu);
  184.     }
  185.  
  186.     sort(queries.begin(), queries.end());
  187.  
  188.     vector<ll> ans(Q);
  189.     active.assign(N,0);
  190.     currentPairs = 0; activeCount = 0;
  191.  
  192.     int L = 0, R = -1;
  193.     for(auto &q: queries){
  194.         while(L > q.l) add_node(euler[--L]);
  195.         while(R < q.r) add_node(euler[++R]);
  196.         while(L < q.l) add_node(euler[L++]);
  197.         while(R > q.r) add_node(euler[R--]);
  198.         if(q.lca != -1){
  199.             add_node(q.lca);
  200.             ans[q.id] = currentPairs;
  201.             add_node(q.lca);
  202.         } else {
  203.             ans[q.id] = currentPairs;
  204.         }
  205.     }
  206.  
  207.     for(int i=0;i<Q;i++) cout << ans[i] << '\n';
  208.  
  209.     return 0;
  210. }
  211.  
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
6 5
3 2 4 1 6 5
1 2
1 3
2 4
2 5
3 6
4 6
5 6
1 1
1 6
6 1
stdout
copy 
9
6
0
3
3
https://ideone.com/s2VIlk
language:
C++14 (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!