T1

原题链接
请注意本题数据提高至5×10^7
很显然，如果一个数n它可以分解为p_1^a_1·p_2^a_2·……·p_m^a_m
则它的约数和为(1+p_1+p_1^2+……+p_1^a_1)·(1+p_2+p_2^2+……+p_2^a_2)·……·(1+p_m+p_m^2+……+p_m^a_m)
本题就是这样，稍微优化一下就可以了。
值得注意的是，QR采取了另一种方法：分段打表。
总的来说，预处理出每一个1e6的sumf的值，则对于每一对询问l,r，暴力寻找离预处理最近的的值就可以了。
并且这个方法竟然比STD还快。%%%

T2

一层一层确定，我们将节点按照深度分为三层，第一层为根节点，方案数为n，第二层至少有[n/2]个节点，若有x个,答案为C(x,n)也就是说子树大小超过的最多只有一棵子树，考虑若是没有限制，则方案数为x^(n-x-1)。
枚举子树大小的最大值y，由于违反限制有y>n/4，可以在任意子树上违反，方案数为x*C(n-x-1,y-1)。
剩余的部分没有限制，方案数为 (x-1)^(n-x-y)。
处理出组合数和幂即可，复杂度O(n^2) 。