素数路径（Prime Distance On Tree ）
题意
边长为1，求长度为素数的路径数。
思路
路径计数：点分治+fft
按深度为下标，次数为值卷起来。
结果会吧两端相同的路径算一次，把两端不同的路径算两次。
因此枚举每个点吧对应深度下标减一。
当然这是那种需要容斥的点分治。
code
点击查看代码
#include
using namespace std;
typedef long long ll;
typedef double db;
const db pi=acos(-1);
const int N=1e6+5;
int rev[N],up,l,nxt[N],to[N],head[N],ecnt,n,smx[N],rt;
int p[N],ptot;
bool is_p[N];
ll ans;
void add_edge(int u,int v) {nxt[++ecnt]=head[u];to[ecnt]=v;head[u]=ecnt;}
struct cop {
db img,rl;
friend inline cop operator*(cop x,cop y) {return (cop){x.img*y.rl+x.rl*y.img,x.rl*y.rl-x.img*y.img};}
friend inline cop operator+(cop x,cop y) {return (cop){x.img+y.img,x.rl+y.rl};}
friend inline cop operator-(cop x,cop y) {return (cop){x.img-y.img,x.rl-y.rl};}
}f[N],g[N];
void FFT(cop *a,int op) {
for(int i=0;ii)swap(a[i],a[rev[i]]);
}
for(int mid=1;mid>1]>>1)|((i&1)<<(l-1));
}
bool vis[N];
int sz[N];
void gt_sz(int u,int fa) {
sz[u]=1;
for(int i=head[u];i;i=nxt[i]) {
int v=to[i];if(v==fa||vis[v])continue;
gt_sz(v,u);sz[u]+=sz[v];
}
}
void gt_rt(int u,int fa,int tot) {
smx[u]=0;
for(int i=head[u];i;i=nxt[i]) {
int v=to[i]; if(v==fa||vis[v])continue;
gt_rt(v,u,tot);
smx[u]=max(smx[u],sz[v]);
}
smx[u]=max(smx[u],tot-sz[u]);
if(smx[u]