晚测6
T1
看见(10^9+)方案数统计，不得不想到矩阵优化，但是看到(nleq1000)，发现好像跑不过？？原因是因为我不知道循环矩阵。。。。wtcl了。
循环矩阵是矩阵的一种，每一行都是上一行移动一次得到的，也就是说，如果将下标从([0,n))，标号，(a_{i,j})对应到第一行就是(a_{0,((j-i+n)\%n+n)\%n})，好吧其实就是左移(i)列，越界就取(mod)。
然后还有一个性质，循环矩阵乘上一个循环矩阵得到的还是一个循环矩阵，所以我们只需要维护矩阵的第一行就行了，然后就能做到(n^2)的乘法，但是(i)不同矩阵也不同，不过可以根据结合率将每(n)个矩阵放到一起，最后把多出来的暴力转移即可。
T2
要求距离最大，也就是尽量把不同的子树内的点分到一起，做法是对于一条边，统计它两侧的询问点个数，取最小值作为贡献，这样得到的一定是一个极大值，至于方案，可以求出一个带权的重心，然后按照(dfn)序进行排序，假设有(2k)个点，将(a_i)与(a_{i+k})进行配对，这样一定可以保证两个点不在同一子树，不然重心就假了。