[Acwing] 1075. 数字转换 树形DP

前言

上海的那一题完全没有想到是树形DP 传送门 :

思路

阅读题目我们可以知道

对于每一个 x x x他可以进行如下转换 :

• 向前 : 他的约数小于他, x → x ( d i v ) \rightarrow x(div) →x(div)
• 向后 : 比他大的约数之和是他 x ( d i v s u m ) = = x x(div_{sum}) ==x x(divsum​)==x

又因为每一个约数之和都是唯一的

所以我们可以让每个数,前后可以转移的地方连一条边

然后问题就转换成 如何求这条数的最大直径

因此就可以返回到 树的直径的树形DP求法

/ 这里的约数处理,我感觉有点魔幻,值得学习 f s u m [ i ∗ j ] + = i fsum[i*j] +=i fsum[i∗j]+=i 表示 i ∗ j i*j i∗j的加上他的约数 j j j

CODE

const int N  = 4e5+10;
vector g[N];

int n ;
int fsum[N];

int d1[N],d2[N],res;
void dfs(int u)
{
	if (d1[u]) return;  
	for(auto  j : g[u])
    {
        dfs(j);
        if (d1[j] + 1 >= d1[u]) d2[u] = d1[u], d1[u] = d1[j] + 1;
        else if (d1[j] + 1 > d2[u]) d2[u] = d1[j] + 1;
    }
    res = max(res, d1[u] + d2[u]);
}
void solve()
{
	cin>>n;
	for(int i=1;i