给定一棵树。对于每个(l)，求有多少对((x,y))满足，(dis(x,y)=l)
容易想到用点分治，对于每棵点分树用fft合并答案，注意要把对应的子树按(size)从小到大排序再依次按对应的大小fft合并。对于单个(n)，时间复杂度(T(n) = sum x_ilog x_i)，且有(sum x_i = n)，可以证明(T(n) = nlog n)，所以总时间复杂度为(O(nlog^2 n))
如果不排序，(T(n) = sum nlog n)，无法通过
给定一棵树。对于每个(l)，求有多少对((x,y))满足，(dis(x,y)=l)
容易想到用点分治，对于每棵点分树用fft合并答案，注意要把对应的子树按(size)从小到大排序再依次按对应的大小fft合并。对于单个(n)，时间复杂度(T(n) = sum x_ilog x_i)，且有(sum x_i = n)，可以证明(T(n) = nlog n)，所以总时间复杂度为(O(nlog^2 n))
如果不排序，(T(n) = sum nlog n)，无法通过