待坑题：
UR1T3：仙人掌上点分治+奇怪的优化
ULR1：阴间题组
UR1T1
发现答案是(sum a_i-(x-1)sumlfloorfrac{a_i}{x} floor)
枚举(x)，尝试快速计算(sumlfloorfrac{a_i}{x} floor)。计算的时候按照长度为(x)分段。
时间(O(mln m))，其中(m=max a_i)。
UR1T2
发现对(x)有影响的是从左往右的一个单调递减子序列（称关键序列）。贪心找关键序列序列（选择最近的一个更小的）。
先对(a_i)从大到小排序，然后DP搞，转移看看每个(a_i)是否在关键序列上。
剩下的问题相当于：假设选入关键序列的数是(a_{b_i})，要将((b_{i-1},b_{i}))中的数插到(b_i)后面的任意位置。
从后往前，相当于(b_i-b_{i-1}-1)个数插入(n-b_i)个数中。写出(O(n^3))DP，简单优化到(O(n^2))。
UR2T1
前缀和之后零点之间看看是否反转即可。
UR2T3
显然可以把(gcd)变成因数，最后反演回来。
先处理祖先后代关系的情况。对于非祖先后代关系的情况：
点分治，计算跨过重心的贡献。分别计算中心（记为(c)）所在的子树的贡献，和(LCA)在中心到根的路径上的贡献。
对于前者，记下子树中各深度点的个数（记为(cnt_i)）。根据((sum a_i)^2=2sum_{i<j} a_{i,j}+sum a_i^2)，分别计算(cnt_c)和(cnt_z,zin son(c))，即可方便计算。这部分时间复杂度显然。
对于后者，枚举(LCA)（设为(x)），记下(x)的子树中除了(c)所在的子树中各深度点的个数。计算时枚举贡献(d)，算出(d)的倍数的深度的点的个数，然后计算(c)子树中的个数，发现这相当于(query(d,r))，询问(c)中(dep_imod d=r)的个数。把这个记忆化即可过。时间复杂度分：前面一步不是问题，问题是计算(query(d,r))。当前分治连通块大小为(S)。当(d< sqrt S)，把所有可能的((d,r))计算出来的总时间是(O(Ssqrt S))；当(d>sqrt S)，计算一次的时间复杂度为(O(frac{S}{d})=O(sqrt S))，由于计算(query(d,r))的总次数为(O(S))，所以总时间也是(O(Ssqrt S))。算上点分治，总时间复杂度还是(O(Ssqrt S))。