SP32093 WTFM - Where The Friends Meet!

· · 题解

本题数据范围有误，参考 SP 的范围：\text{GDP} \leq 10^{6}。

其实就是将质因数分解与树前缀和缝在一起。

考虑 \Theta(n) 地预处理这个不同质因数个数。可以想到由一个最大的因数转移，故用类似线性筛的方法预处理每个数的最小质因数，即只更新没有被更小的质数更新过的数。然后每次除以最小质因数，进行转移即可。

在树中，城市 a 到 b 的路径，可以看作 a,b 分别到根的路径，去掉它们的 LCA 到根的路径。故若某个位置的 GDP 满足不同质因数个数至少 k 的限制，则该位置的值为 1，处理到根的前缀和。询问时再进行推算即可。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pr pair<int,int>

const int N = 1e5 + 5, maxv = 1e6;

int n, k, q, gd[N], minv[maxv + 5], cnt[maxv + 5], sum[N], st[N][18], dep[N];
bool val[N];
vector<int> G[N];

void calc(){
    for(int i = 1; i <= maxv; ++ i) minv[i] = i;
    for(int i = 2; i * i <= maxv; ++ i) if(minv[i] == i)
        for(int j = i * i; j <= maxv; j += i) if(minv[j] == j)
            minv[j] = i;

    for(int i = 2; i <= maxv; ++ i){
        int pri = minv[i], j = i / pri;
        cnt[i] = cnt[j] + (j % pri != 0);
    }
}

void dfs(int u, int fa){
    dep[u] = dep[fa] + 1, st[u][0] = fa, sum[u] = sum[fa] + val[u];
    for(int v: G[u]) if(v != fa) dfs(v, u);
}

void initst(){
    for(int j = 1; (1 << j) <= n; ++ j)
        for(int i = 1; i <= n; ++ i) st[i][j] = st[st[i][j - 1]][j - 1];
}

int LCA(int u, int v){
    if(dep[u] < dep[v]) swap(u, v);
    for(int j = 17; j >= 0; -- j)
        if(dep[st[u][j]] >= dep[v]) u = st[u][j];
    if(u == v) return u;
    for(int j = 17; j >= 0; -- j)
        if(st[u][j] != st[v][j]) u = st[u][j], v = st[v][j];
    return st[u][0];
}

signed main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    calc();

    while(cin >> n >> k >> q){
        for(int i = 1; i <= n; ++ i)
            cin >> gd[i], val[i] = (cnt[gd[i]] >= k);
        for(int i = 1, u, v; i < n; ++ i){
            cin >> u >> v;
            G[u].push_back(v), G[v].push_back(u);
        }

        dfs(1, 0), initst();
        while(q --){
            int a, b;
            cin >> a >> b;
            int l = LCA(a, b);
            cout << sum[a] + sum[b] - 2 * sum[l] + val[l] << "\n";
        }
    }

    return 0;
}