怎么评价这个题呢……是自己做出来了，但做完之后感觉无法理解自己的做法，因为我是 DS 菜鸡嘛……想了一会儿之后，来写了这个题解。
要处理 (gcd)，考虑分解质因数。然后链上每个数对答案的贡献就是它每个质因子的次数与 (w) 的该质因子的次数取个 (min)。
我们考虑树剖。于是问题转化到区间上。注意到任意一个数的质因子个数是 (mathrm O(log v)) 级别的，那么直接枚举 (w) 的每个质因子。于是问题转化为如何计算一个区间上某个质因子的次数们与给定数的 (min) 的和。直接 DS 维护貌似不太可做，但注意到次数也是 (mathrm O(log v)) 级别的，于是我们枚举次数。于是问题转化为如何计算一个区间上某个质因子次数为给定数的个数。这个就比较好办了，在预处理分解质因数的时候，把这些质因子的次数压入质因子所对应的 vector，每个 vector 记录前缀和，然后在里面二分。然后这个二分操作是和枚举次数平行的，数一下发现是 3log。
注意到这是个静态问题，于是想到树上前缀和 instead of 树剖。依然枚举 (w) 的质因子，对于每个质因子依然枚举次数（这样 (sumalpha) 依然是 1log 级别的，前面虽然也涉及到这个 (sumalpha)，但还有一个二分强制增加了一个 log）。于是我们现在想知道的是一条链上某个质因子次数为给定数的个数。考虑对这个进行前缀和。但是要是在树的某处都放一个前缀和的数组的话，那时空都会炸，但是注意到这是有可优化性的，因为总共更新前缀和的次数是不会炸的，炸的是复制粘贴数组的代价。于是我们考虑惯用套路：在 DFS 的过程中实时维护前缀和数组，该回溯回溯，这个类似于扫描线的思想。然后将需要查询前缀和的地方给标记到对应节点上，到时贡献给相应询问。这样子是 1log 的。
除此之外还有一些小细节。分解质因数的根号复杂度要算上。前缀和算 lca 需要树上倍增。还要把质数筛一下来缩小值域，不然数组开不下。总的来说挺难写的。