算法分析
这是一道把数论和树论放在一起的综合题
记 f(x)
表示所有由点权都是 $x$ 的倍数的点构成的树链中的长度的最大值
记 g(x)
表示所有由点权的最大公约数恰等于 $x$ 的点构成的树链中的长度的最大值
注意到对于 $x$ 的某个因子 $y$,一定有 $f(y) \geqslant g(x)$
于是,原问题可转化为求 $\max(f(1), f(2), \cdots, f(2e5))$
然后发现超时。。。
事实上,我们只需枚举 $2 \sim 2e5$ 之间的素数即可
然后接下来到了树论部分:
我们只需对树上所有点权是 $x$ 的倍数的点进行染色,这样就形成了若干个连通块
我们只需遍历每个连通块,求出它的直径即可
对于连通块,也可以看成是树,跑 $2$ 遍 $\operatorname{dfs}$ 就能求出直径
C++ 代码
#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using namespace std;
using P = pair<int, int>;
using ll = long long;
template<class T=int>
inline T read() {
T num = 0;
int neg = 0;
char c = getchar();
while (!isdigit(c) and c != '-') {
c = getchar();
}
if (c == '-') neg = 1;
else num = c-'0';
c = getchar();
while (isdigit(c)) {
num = (num<<1)+(num<<3)+(c^48);
c = getchar();
}
return num;
}
const int M = 200001;
struct Sieve {
int n;
vector<int> f, primes;
Sieve(int n=1): n(n), f(n+1) {
f[0] = f[1] = -1;
for (ll i = 2; i <= n; ++i) {
if (f[i]) continue;
primes.push_back(i);
f[i] = i;
for (ll j = i*i; j <= n; j += i) {
if (!f[j]) f[j] = i;
}
}
}
};
int main() {
vector<int> ps;
{
Sieve s(M);
ps = s.primes;
}
int n = read();
vector<int> a(n);
rep(i, n) a[i] = read();
vector<vector<int>> is(M);
rep(i, n) is[a[i]].push_back(i);
for (int p : ps) {
for (int i = 2*p; i < M; i += p) {
is[p].insert(is[p].end(), is[i].begin(), is[i].end());
}
}
vector<vector<int>> to(n);
rep(i, n-1) {
int a = read(), b = read();
--a; --b;
to[a].push_back(b);
to[b].push_back(a);
}
vector<int> f(M);
vector<bool> live(n);
vector<bool> used(n);
for (int x : ps) {
vector<int>& vs = is[x];
for (int v : vs) live[v] = true;
auto dfs = [&](auto f, int v, int d=1, int p=-1) -> P {
used[v] = true;
P res(d, v);
if (p == -1) res = P(1, -1);
for (int u : to[v]) {
if (u == p or !live[u]) continue;
res = max(res, f(f, u, d+1, v));
}
return res;
};
for (int v : vs) if (!used[v]) {
int a = dfs(dfs, v).second;
int b = 0;
if (a == -1) b = 1;
else b = dfs(dfs, a).first;
f[x] = max(f[x], b);
}
for (int v : vs) used[v] = false;
for (int v : vs) live[v] = false;
}
int ans = 0;
for (int x : ps) {
ans = max(ans, f[x]);
}
cout << ans << '\n';
return 0;
}