官方题解只能做到 $O\left(\frac{n}{\log^2 n}\right)$？玩的太差了。可以做到 $O\left(\frac{n^{2/3}}{\log^{1/3} n)}\right)$ 时间、$O\left(\frac{n^{2/3}}{\log^{4/3} n}\right)$ 空间。
数学转化
记 $h(v)$ 为 $v$ 的最小质因子，$s(v)$ 为以 $v$ 为根的子树大小。题目中的父亲关系是 $v\to v/h(v)$，并且 $n\le 10^{10}$，不能显式建树。([QOJ][2])
删去连接 $v$ 和父亲的边后，树被分为大小为 $s(v)$ 和 $n-s(v)$ 的两部分，因此答案为
$$ \mathrm{Ans}=\sum_{v=2}^{n}s(v)\bigl(n-s(v)\bigr). $$
定义 $F_p(t)$ 为不超过 $t$、所有质因子都不超过 $p$ 的正整数个数，其中包含 $1$。
设 $h(v)=p$。一个数是 $v$ 的后代，当且仅当它可以写成 $va$，且 $a$ 的所有质因子都不超过 $p$：向父亲移动时不断删除最小质因子，恰好可以先删去 $a$ 的全部质因子。因此，$s(v)=F_p(\lfloor n/v\rfloor)$。
将最小质因子为 $p$ 的顶点唯一表示为 $v=p^e x$，其中 $e\ge1$，且 $x=1$ 或 $h(x)>p$。固定 $p,e$，令 $m=\lfloor n/p^e\rfloor$，则它们的子树大小为 $F_p(\lfloor m/x\rfloor)$。
为了统计合法的 $x$，再定义 $G_p(t)$：在 $2,\ldots,t$ 中，删去最小质因子不超过 $p$ 的合数，剩余整数的个数。注意，所有质数始终保留。
于是，当 $p< l\le r$ 时，区间 $[l,r]$ 中满足 $h(x)>p$ 的整数个数恰好为 $G_p(r)-G_p(l-1)$。保留下来的小质数都不在这个区间内，不会影响计数。
现在对 $x>p$ 整除分块。设当前块为 $[l,r]$，$t=\lfloor m/l\rfloor$，$r=\lfloor m/t\rfloor$，并记 $c=G_p(r)-G_p(l-1)$。这一块的贡献就是 $cF_p(t)(n-F_p(t))$。至于 $x=1$，单独加入 $F_p(m)(n-F_p(m))$。
只需逐个处理 $p\le\sqrt n$。如果 $h(v)>\sqrt n$，那么 $v$ 不可能是合数，只能是质数 $p$，且其子树大小直接等于 $\lfloor n/p\rfloor$。这一部分在所有筛法结束后，利用质数计数函数 $\pi$ 再做一次整除分块即可。
批量维护与复杂度
记 $L=\log n$，选择分界
$B=\Theta!\left(n^{2/3}/L^{4/3}\right)$，
并保证 $B\ge\lfloor\sqrt n\rfloor$。再令 $M=\lfloor n/(B+1)\rfloor$。
所有超过 $B$ 的查询参数都形如 $\lfloor n/d\rfloor$，其中 $d\le M$。这是因为 $\lfloor\lfloor n/a\rfloor/b\rfloor=\lfloor n/(ab)\rfloor$，而整除分块的右端点也具有同样的形式。
所以，小参数 $1,\ldots,B$ 用稠密数据结构维护；大参数只维护 $M$ 个整除商。由于 $B\ge\sqrt n$，这些大整除商互不相同，可以用 $d=\lfloor n/t\rfloor$ 直接定位，无须哈希表。
小参数不做逐质数、逐状态的动态规划，而是维护两个集合的指示数组。
对于 $F_p$，初始集合只有 $1$，处理质数 $p$ 时，加入最大质因子恰好为 $p$ 的整数。对于 $G_p$，初始集合是 $2,\ldots,B$，处理 $p$ 时，删去最小质因子恰好为 $p$ 的合数。
两个集合分别使用树状数组维护前缀计数。线性筛预处理每个整数的最小质因子、最大质因子和 $\pi(t)$。每个整数最多被加入、删除各一次，因此小参数部分总共只需要 $O(B\log B)$ 时间，而不是 $O(B\pi(\sqrt n))$。
下面说明大参数如何维护，以及哪些查询可以跳过树状数组。
对于 $G$，设当前质数是 $p$，之前已经处理了 $j$ 个质数。对 $v\ge p^2$，有转移 $G_{\mathrm{new}}(v)=G_{\mathrm{old}}(v)-G_{\mathrm{old}}(\lfloor v/p\rfloor)+j$；对 $v< p^2$，无需修改。
这是因为本轮删去的数恰好是 $pb$，其中 $b\ge p$，且 $b$ 没有小于 $p$ 的质因子。$G_{\mathrm{old}}(\lfloor v/p\rfloor)$ 中额外保留了之前的 $j$ 个质数，将它们扣除即可。
大状态按分母 $d$ 递增的顺序更新，保证转移读取上一层；之后才修改小范围的树状数组。
这里有一个非常重要的捷径：处理 $p$ 之前，所有未删去的合数都不小于 $p^2$。 因而，当转移来源 $t< p^2$ 时，直接返回预处理的 $\pi(t)$，不必查询树状数组。处理完 $p$ 后，$t\le p^2$ 也可以这样处理。
对于 $F$，转移为 $F_p(v)=F_{\mathrm{prev}}(v)+F_p(\lfloor v/p\rfloor)$。先更新小范围的集合，再按分母 $d$ 递减的顺序更新大状态，就能得到当前层的转移来源。
但不能让全部大状态一直更新下去。
分母为 $d$ 的状态，最终需要的是 $F_{h(d)}(\lfloor n/d\rfloor)$。因此，质数处理到 $h(d)$ 后，这个状态就可以停止更新。用一个按 $d$ 递减排列的活跃数组维护这些状态，每轮顺便原地过滤，不能仍然扫描整个数组再判断是否活跃。
转移来源的分母是 $dp$。对于仍活跃的 $d$，有 $h(d)\ge p$，所以 $h(dp)=p$：来源状态恰好在当前轮完成。这也说明停止更新已经完成的状态是安全的。
还可以提前补完质数分母的状态。
设分母 $q$ 是质数，令 $m=\lfloor n/q\rfloor$。处理到某个 $p< q$ 时，如果 $\lfloor m/p\rfloor\le p$，那么对于之后的任意质数 $r>p$，都有 $F_r(\lfloor m/r\rfloor)=\lfloor m/r\rfloor$。
于是，可以直接给当前状态补上 $\sum_{p< r\le q,\ r\text{ 为质数}}\lfloor m/r\rfloor$，得到它在质数 $q$ 这一轮的最终值，然后永久移出活跃集合。
这个和利用整除分块和预处理的 $\pi$ 计算即可，因为 $r\le q\le M\le B$。提前写入最终值不会污染其他转移：别人的转移来源分母为 $dp$，必然是合数，不会读取质数分母 $q$ 的中间状态。
最后，统计贡献时还有两个必须保留的判断：
当 $t\le p$ 时，直接使用 $F_p(t)=t$；当一个整除块的合法整数数量为零时，直接跳过，不查询 $F$。
第二个判断也关系到状态有效性。当 $t>B$ 时，整除块只能包含一个 $x$；只有该块非空，才能保证对应分母 $p^e x$ 的最小质因子就是当前的 $p$，从而访问正确阶段的 $F$。
下面计算复杂度。这里只使用 $\pi(t)=O(t/\log t)$，不需要假设质数随机分布。
小范围维护的代价为 $O(BL)$。
大范围 $G$ 的转移次数为 $\sum_p O(\min(M,n/p^2))=O(n/(\sqrt B,L))$。真正需要查询树状数组的转移，还必须满足来源 $\lfloor n/(dp)\rfloor\ge p^2$，即 $d\le n/p^3$。所以这些树状数组查询的总代价只有 $O!\left(L\sum_p\min(M,n/p^3)\right)=O(n/B^{2/3})$。
大范围 $F$ 中，合数分母至多更新到 $\sqrt M$ 以内的质数，其总代价可以上界为 $O(M^{3/2})$。质数分母 $q$ 在处理到约 $\sqrt{n/q}$ 时就会被提前补完，因此更新部分的总代价为 $O!\left(L\sum_{q\le M,\ q\text{ 为质数}}\pi(\sqrt{n/q})\right)=O(n/(\sqrt B,L))$。提前补完每个 $q$ 至多枚举 $O(\sqrt{n/q})$ 个整除块，求和后同样是 $O(n/(\sqrt B,L))$。
剩下的是统计贡献的整除分块。固定 $p,e$，块数为 $O(\min(\sqrt{n/p^e},n/p^{e+1}))$，总块数为 $O(n^{2/3}/L)$。但不能直接给每块乘一个树状数组查询的 $O(L)$，否则只得到 $O(n^{2/3})$。
对于 $G$ 查询，只有块的右端点超过 $p^2$ 才可能访问树状数组。$e=1$ 时，这类块数不超过 $O(\min(\sqrt{n/p},n/p^3))$，对质数求和并乘上查询代价后是 $O(n^{3/5})$。$e\ge2$ 的全部块数只有 $O(\sqrt n\log\log n)$，也是较小项。
对于 $F$ 查询，令 $X=\sqrt B$。当 $p\le X$ 时，所有块数之和为 $O(\sqrt{nX}/L)$。当 $p>X$ 时，只有非空且 $t>p$ 的块才需要查询；其中合法的 $x$ 满足 $p< x\le n/p^2$。因为 $X\ge n^{1/4}$，这样的 $x$ 不可能是合数，只能是质数。因此，这部分查询次数至多为 $\sum_{X< p\le n^{1/3}}\pi(n/p^2)=O(n/(XL^2))$。
乘上树状数组的查询代价，统计贡献中的 $F$ 查询总时间为 $O(\sqrt n,B^{1/4}+n/(\sqrt B,L))$。
代入 $B=\Theta(n^{2/3}/L^{4/3})$，主要的三项 $BL$、$n/(\sqrt B,L)$、$\sqrt n,B^{1/4}$ 都是 $n^{2/3}/L^{1/3}$，其余项渐近更小，最终得到
$$ T(n)=O\!\left(\frac{n^{2/3}}{(\log n)^{1/3}}\right), \qquad S(n)=O\!\left(\frac{n^{2/3}}{(\log n)^{4/3}}\right). $$