题解：P15608 [ICPC 2021 Jakarta R] Not One

· · 题解

前言

肯定是因为我太菜了）这道题卡了我两天，发个题解纪念一下。

题目大意

给你一棵树，每个点有权值 a_i。让你找一棵连通子树，满足子树内所有数的最大公约数，求最大大小；不存在输出 0。

乍一看好像是一道树形 dp，然后你就会喜提第六个测试点 Wrong Answer。

聪明的你拿起放大镜仔细观察，发现这道题有一些特殊的东东：若一棵子树每个节点的最大公约数大于一，那么，一定存在一个质数 p，使得 p 整除该子树里所有的数。

那么！问题就可以转化为：对于每个质数 p，只保留树上能够被 p 整除的节点，形成一个子图。求该子图中最大联通块的大小，然后每个质数的答案取最大值。

解题思路

  1. 用线性筛预处理出 10^6 以内所有的质数（这很简单就不讲了）。
  2. 对于每个节点的权值 a_i，分解其质因子（这也很简单应该不用细讲吧）。然后建立一个映射关系：每个质数 p 与所有权值拥有质因子 p 的节点形成映射。
  3. 对于每个质数 p，按照前面的想法，在树上只看权值的质因子包含 p 的节点，求这些点形成的子图（其实是森林）中最大联通块的大小。注意！ 这里使用朴素的遍历会喜提绿黑大礼包（AC 和 TLE），所以我们需要采用时间戳染色进行优化，这个不会的建议先学一下这道题。我们遍历所有质数 p 的映射表，遇到未访问的节点就进行 bfs 搜索，对于遍历到的每个节点 u，只走到与之相邻且一样权值含有质因子 p 的节点，并统计联通块大小，并打擂台取最大值。

时间复杂度为 \Theta(N\log A)，A 为所有点中的最大权值。

其余步骤详见代码及注释。

代码

终于到你们最爱看的代码了。。。马蜂有点猎奇请见谅！

/*
    Author: Enoch2013
    Time: 2026.7.22 10:21:09 (a.m.)
    Using Windows10 at Quanzhou,Fujian Province
*/
#include <bits/stdc++.h>
#define pb push_back
#define rep(x, y, z) for (int x = (y); x <= (z); x++)
#define per(x, y, z) for (int x = (y); x >= (z); x--)
#define mem(a, b) memset((a), (b), sizeof (a))
using namespace std;
using vi = vector<int>;
// 快读快写不用说了。
inline int read()
{
    int ans = 0;
    char ch = getchar();
    while (!isdigit(ch))
        ch = getchar();
    while (isdigit(ch))
        ans = (ans << 3) + (ans << 1) + (ch ^ 48), ch = getchar();
    return ans;
}
inline void write(int x)
{
    if (x > 9)
        write(x / 10);
    putchar(x % 10 + '0');
}
const int N = 1e6 + 10;
bool is_pr[N]; // 标记是否为质数
// a[] 为输入的权值，bfn[] 为访问标记数组（配合时间戳使用）。
// 当 bfsn[u] == cnt 时表示节点 u 为当前质数 p 的可选节点，cnt 记录时间戳，lmao 存储映射关系，详见上文。
int n = read(), a[N], bfn[N], bfsn[N], cnt, ans; vi g[N], lmao[N], prime; inline void add(int u, int v) { g[u].pb(v), g[v].pb(u); } // 双向建边
inline void init() // 线性筛不用讲了吧。。。
{
    mem(is_pr, 1), is_pr[0] ^= 1, is_pr[1] ^= 1;
    rep(i, 2, N - 10)
    {
        if (is_pr[i]) prime.pb(i);
        for (auto &qp : prime) // qp！（bushi
        {
            if (qp > (N - 10) / i) break;
            is_pr[i * qp] ^= 1;
            if (!(i % qp)) break;
        }
    }
}
inline vi get(int x) // 分解质因子应该也不用讲了吧。。。
{
    vi res;
    if (x == 1) return res;
    for (auto &qp : prime) // qp * 2
    {
        if (qp > x / qp) break;
        if (!(x % qp)) { res.pb(qp); while (!(x % qp)) x /= qp; }
    }
    if (x > 1) res.pb(x);
    return res;
}
inline void bfs(int S) // 利用广搜求联通块大小（不用 dfs 是因为怕爆栈
{
    queue<int> q; q.push(S); bfn[S] = cnt; // 标记访问
    int sz = 0; // 该联通块的大小
    while (q.size())
    {
        int u = q.front(); q.pop(); sz++;
        for (auto &to : g[u]) if (bfn[to] != cnt && bfsn[to] == cnt) bfn[to] = cnt, q.push(to); // 未被本轮访问且为可选节点 
    }
    ans = max(ans, sz); // 打擂台取最大值
}
int main()
{
    init();
    rep(i, 1, n)
    {
        a[i] = read();
        for (auto &qp : get(a[i])) lmao[qp].pb(i); // 建立映射关系。qp * 3（？？？
    }
    rep(i, 1, n - 1) { int u = read(), v = read(); add(u, v); } // 建树
    rep(i, 2, N - 10) // 遍历所有数
    {
        if (lmao[i].empty()) continue; // 没有映射关系就跳过
        cnt++; // 时间戳加一
        for (auto &u : lmao[i]) bfsn[u] = cnt; // 本轮可选节点
        for (auto &S : lmao[i]) if (bfn[S] != cnt) bfs(S); // 遍历子图（森林）求联通块大小
    }
    write(ans); putchar('\n'); // 输出答案
    return 0;
}

完结散花！