贪心+预处理

首先说一下一个简单的贪心
在枚举$x$的子树时，相当于枚举$x$的因子$y(y!=1)$
再遍历$(x/y)$树
若$y$不为质数，则$y$必可以拆分成两个大于1的数$p,q$
当$y=p$或$y=q$时包含了原树且多了一个节点，肯定有更优方案
故我们枚举的$y$必为质数

Part1:P50

注意到每个数所对应的因子树都是确定的
一个数为多颗树的子树，也就是说被询问到多次，即重复子问题
检测到DP关键词，于是考虑DP

对于任意一个$x\in[1,1e6]$,所含质因子的个数不超过8个
可以先预处理出每个数的质因子，在转移时直接枚举质因子即可

Part2:P70

一个数的因子不超过$2\sqrt x$
也就是说我们在DP时展开的树不会超过2e6个
离散后DP即可

Part3:P100

对于如此大的数据范围，继续DP显然是不够的
然而，对于这类考虑因子的题，每个数的因子情况都不相同
显然对于每个数都要单独决策
在回顾先前的DP写法，在决策除去哪个质数时,枚举了所有质因数
导致DP所展开的树迅速增大，于是继续考虑贪心，直接得出最优的质因数

是删去指数最大的质因数啦

证明:
设$x= a_1^{b_1} \cdot a_2^{b_2} …..$
设删除一个$a_1$的操作在删除$a_2$后且$b_1>b_2$,当前$x$的因子总数为$tot$
$ans+=tot/(b_2+1)\times b_2+tot/(b_2+1)\times b_2/(b_1+1)\times b_1$
若先删除 $a_1$
则有 $ans+=tot/(b_1+1)\times b_1+tot/(b_1+1)\times b_1/(b_2+1)\times b_2$
显然先删除 $a_1$的操作对答案贡献更大，且接下来的子树相同

于是就可以预处理出$[A,B]$区间内的数的质因数
查询时用一个数据结构维护指数的最大值模拟删除即可

关于预处理，只需要在筛$1e6$以下素数的时候同时像埃氏筛一样循环一遍$[A,B]$即可
时间复杂度$O(nln(n))$