CodeChef - PRIMEDST (点分治/DSU+FFT)

题目的本质是要求每种距离的点对的个数

考虑使用点分治+FFT来维护

对于当前点分根以及周围的所有点,构造\(f(x)=\sum x^{dep_x}\)求平方即可，对于每颗子树容斥

复杂度就是所有的\(Size\)之和乘上\(\log n\)，即\(n\log^2 n\)

最后把距离是质数的算出来即可

(代码太丑了)

#include
using namespace std;

//#define double long double

#define reg register
typedef long long ll;
#define rep(i,a,b) for(reg int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(reg int i=a,i##end=b;i>=i##end;--i)

template  inline void cmin(T &a,T b){ ((a>b)&&(a=b)); } 
template  inline void cmax(T &a,T b){ ((a