题解：P12001 在小小的奶龙山里面挖呀挖呀挖

CuFeO4 · 2025-03-29 19:01:08 · 题解

比题解更无脑的做法。

请注意算法常数对时间效率的影响。

加上 5s 时限，说明如果常数够小可以通过。

发现 10^5 以内的素数只有 10^4 个，发现不能开 n\times 10^4 的数组，那么将询问离线下来，对于每个素数考虑，树上差分维护。假设当前处理素数 p，记 ct_x 表示 1\sim x 路径上的点有多少个 a_i 满足 p 整除 a_i。这个显然可以 dfs O(n) 更新。

但是 dfs 更新太慢了，考虑卡常经典操作，将树拍成 dfs 序更新即可，求 LCA 用的 ST 表，最大点不超过一坤秒。

#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t;i += p)
#define drep(i,s,t,p) for(int i = s;i >= t;i -= p)
#ifdef LOCAL
  auto I = freopen("in.in","r",stdin),O = freopen("out.out","w",stdout);
#else
  auto I = stdin,O = stdout;
#endif
using ll = long long;using ull = unsigned long long;
using db = double;using ldb = long double;
const int N = 5e4 + 10;
#define eb emplace_back
vector<int> e[N],prime;
bitset<100010> vis;
int ct[N],n,m,a[N],u[N],v[N],dfn[N],tim,st[18][N],ans[N],lca[N],F[N],rdfn[N];
void shai(int n){
    for(int i = 2;i <= 100000; ++i){
        if(!vis[i]) prime.emplace_back(i);
        for(auto j:prime){
            if(i * j > n) break;
            vis[i * j] = true;
            if(i % j == 0) break;
        }
    }
}
void dfs(int x,int fa){
    st[0][dfn[x] = ++tim] = fa;F[x] = fa;
    rdfn[tim] = x;
    for(auto y:e[x]) if(y ^ fa) dfs(y,x);
}
int get(int x,int y){return dfn[x] < dfn[y]?x:y;}
int LCA(int x,int y){
    if(x == y) return x;
    if((x = dfn[x]) > (y = dfn[y])) swap(x,y);
    int k = __lg(y-x++);
    return get(st[k][x],st[k][y-(1<<k)+1]);
}
void pdfs(const int &now){
    for(int i = 1;i <= n; ++i){
        int x = rdfn[i];
        ct[x] = ct[F[x]];
        ct[x] += a[x]%now == 0;
    }
}
signed main(){
  cin.tie(nullptr)->sync_with_stdio(false);
    shai(100000);
    cin>>n>>m;
    for(int i = 1;i <= n; ++i) cin>>a[i];
    for(int i = 1,u,v;i < n; ++i) cin>>u>>v,e[u].eb(v),e[v].eb(u);
    dfs(1,0);
    for(int j = 1;j <= __lg(n); ++j)
        for(int i = 1;i + (1 << j) - 1 <= n; ++i)
            st[j][i] = get(st[j-1][i],st[j-1][i+(1<<(j-1))]);
    for(int i = 1;i <= m; ++i){
        cin>>u[i]>>v[i],lca[i] = LCA(u[i],v[i]);
    }
    for(auto now:prime){
        pdfs(now);
        for(int i = 1;i <= m; ++i){
            if(ct[u[i]] + ct[v[i]] - ct[lca[i]] - ct[F[lca[i]]]){
                ans[i]++;
            }
        }
    }
    for(int i = 1;i <= m; ++i) cout<<ans[i]<<'\n';
}