<—点个赞吧QwQ
宣传一下算法提高课整理{:target=”_blank”}
树形DP
某两个数$x$和$y$可以互相转化,相当于某图结构中$x$和$y$代表的两个节点可以互相到达,关键问题就是如何确定这是个树结构
很显然,每个数$x$的约数之和$y$是唯一确定的,由于只有y比x小才能转换,故这种转换关系可以抽象为“每一个比$x$小的确定值$y$,都只有唯一的前驱$x$”,和树结构的定义完全一致
接下来,问题就转换为了“求树中任意节点之间距离的最大值”,详情请见注释,也可以参考incra的题解来求解这个问题
时间复杂度
$O(n)$,其中n是节点总数
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 50005;
int n = 0, tot = 2, ans = 0;
int fin[N << 1], nxt[N << 1], last[N], vis[N];
int main() {
//求约数之和
auto sumOfDivisor = [=](int dv) {
//特判1,2
if(dv < 3) return dv - 1;
int sum = 1;
for(int i = 2; i * i <= dv; i++) {
if(dv % i == 0) {
sum += dv / i;
//相同的约数不能加两次
if(i * i != dv) sum += i;
}
}
return sum;
};
//单向连接
auto _connect = [=](int s, int e) {
fin[tot] = e;
nxt[tot] = last[s];
last[s] = tot++;
};
//双向连接(无向连接 = 正反双向连接)
auto connect = [=](int s, int e) {
_connect(s, e);
_connect(e, s);
};
int n;
cin>>n;
for(int i = 2;i <= n;i++) {
int s = sumOfDivisor(i);
//约数之和比本身小,代表两个数所代表的节点之间有双向连接
if(s < i) connect(s, i);
}
//求以某个节点为根的子树中能贡献出的单边最长路径
//同时求整个树结构中最长路径的长度
auto dfs = [&](auto&& dfs, int cur)-> int {
if(cur == 0) return 0;
//最大值和次大值,在子树中取
int fst = 0, scd = 0;
vis[cur] = 1;
for(int i = last[cur];i != 0;i = nxt[i]) {
int nx = fin[i];//与nxt区别开
if(vis[nx] == 1) continue;
//要算上当前走过的这条边
int dist = dfs(dfs, nx) + 1;
if(dist >= fst) {
scd = fst;
fst = dist;
}
else if(dist >= scd) scd = dist;
}
//以当前节点为根的子树中最长路径的长度
//相当于当前节点的子树中最长的两条单边路径的长度之和
ans = max(ans, fst + scd);
//返回最长单边路径以参与其他节点的讨论
return fst;
};
//可以忽略返回值
dfs(dfs, 1);
cout << ans << endl;
return 0;
}