5.15 省选模拟赛 T1 点分治 FFT

LINK:5.15 T1

对于60分的暴力 都很水 就不一一赘述了.

由于是询问所有点的这种信息 确实不太会.

想了一下 如果只是询问子树内的话 dsu on tree还是可以做的。

可以自己思考一下.

如果强行dsu的时候做 会发现点对和点对之间难以解决。

考虑正解 点分治：

当x为分治中心还是需要统计点对和点对之间的贡献.

和刚才几乎一样.不过这个时候可以发现 需要对每个点都求一个答案.

对于深度为w的点 那么 贡献为\(\sum_{j=w}^{n}c_{j-w}a_j\)

其中\(c_x\)表示当前深度为x的点的个数 不过这个可能统计到自己的那条链中的答案.

不过可以再对每个子树内做一遍 减掉即可。

那么我们发现这样做的话 每一个深度的点 答案其实是一样的.

这样对于上面的东西 其实可以看成是一个卷积.

这个卷积比较奇特 是相减的形式 可以变形 两边同时加上n-1就变成了正常的卷积。

对于重复的 可以发现可以被减掉 所以这样做事正确的。

值域原因 不能使用NTT 所以上FFT 常数太大可以选择预处理单位根.

const int MAXN=600010;

const db Pi=acos(-1.0);

int n,root,lim,len;

int w[MAXN],sz[MAXN],son[MAXN],c[MAXN],ans[MAXN],vis[MAXN];

int lin[MAXN],ver[MAXN],nex[MAXN],rev[MAXN],v[MAXN],d[MAXN];

struct wy

{

	db r,v;

	wy(db x=0,db y=0){r=x;v=y;}

	wy friend operator *(wy a,wy b){return wy(a.r*b.r-a.v*b.v,a.r*b.v+b.r*a.v);}

	wy friend operator +(wy a,wy b){return wy(a.r+b.r,a.v+b.v);}

	wy friend operator -(wy a,wy b){return wy(a.r-b.r,a.v-b.v);}

}A[MAXN],B[MAXN],w0[20][MAXN],w1[20][MAXN];

inline void add(int x,int y)

{

	ver[++len]=y;nex[len]=lin[x];lin[x]=len;

	ver[++len]=x;nex[len]=lin[y];lin[y]=len;

}

inline void get_root(int x,int fa,int n)

{

	sz[x]=1,son[x]=0;

	go(x)if(tn!=fa&&!vis[tn])

	{

		get_root(tn,x,n);

		sz[x]+=sz[tn];

		son[x]=max(son[x],sz[tn]);

	}

	son[x]=max(son[x],n-sz[x]);

	if(son[x]<son[root])root=x;

}

inline void get_dis(int x,int fa,int dep)

{

	d[x]=dep;++c[d[x]];

	go(x)if(tn!=fa&&!vis[tn])get_dis(tn,x,dep+1);

}

inline void FFT(wy *a,int op)

{

	rep(0,lim-1,i)if(i<rev[i])swap(a[i],a[rev[i]]);

	for(int len=2,cc=0;len<=lim;len=len<<1,++cc)

	{

		int mid=len>>1;

		for(int j=0;j<lim;j+=len)

		{

			for(int i=0;i<mid;++i)

			{

				wy x=a[i+j],y=a[i+j+mid]*(op==-1?w1[cc][i]:w0[cc][i]);

				a[i+j]=x+y;a[i+j+mid]=x-y;

			}

		}

	}

	if(op==-1)rep(0,lim-1,i)a[i].r=a[i].r/lim;

}

inline void js(int n)

{

	reverse(c,c+n);

	int sz1=n,sz2=n+n-1;

	lim=1;

	while(lim<sz1+sz2-1)lim=lim<<1;

	rep(0,lim-1,i)rev[i]=rev[i>>1]>>1|((i&1)?lim>>1:0);

	rep(0,sz1-1,i)A[i]=wy(c[i],0);rep(sz1,lim-1,i)A[i]=wy(0,0);

	rep(0,sz2-1,i)B[i]=wy(w[i],0);rep(sz2,lim-1,i)B[i]=wy(0,0);

	FFT(A,1);FFT(B,1);

	rep(0,lim-1,i)A[i]=A[i]*B[i];

	FFT(A,-1);

	rep(0,n-1,i)v[i]=(int)(A[i+n-1].r+0.5);

}

inline void get_ans(int x,int fa,int op)

{

	if(op)ans[x]+=v[d[x]];

	else ans[x]-=v[d[x]];

	go(x)if(tn!=fa&&!vis[tn])

	get_ans(tn,x,op);

}

inline void solve(int x,int n,int op)

{

	if(op)

	{

		rep(0,n,i)c[i]=0;

		get_dis(x,0,1);

		js(n+1);

		get_ans(x,0,0);

	}

	//if(dep>30){cout<<"ww"<<endl;exit(0);}

	root=0;get_root(x,0,n);

	//cout<<root<<' '<<son[root]<<' '<<sz[root]<<endl;

	rep(0,n,i)c[i]=0;

	get_dis(root,0,0);

	vis[root]=1;js(n);

	get_ans(root,0,1);

	int ww=root;

	go(ww)

	if(!vis[tn])

	{

		//cout<<(sz[tn]>sz[ww]?n-sz[ww]:sz[tn])<<endl;

		solve(tn,sz[tn]>sz[ww]?n-sz[ww]:sz[tn],1);

	}

}

int main()

{

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

	get(n);

	rep(0,n-1,i)get(w[i]);

	rep(2,n,i)add(read(),read());

	for(int i=2,j=0;j<20;i=i<<1,++j)

	{

		int mid=i>>1;

		wy wn=wy(cos(Pi/mid),sin(Pi/mid));

		wy d=wy(1,0);

		for(int k=0;k<mid;++k)

		{

			w0[j][k]=d;w1[j][k]=d;

			w1[j][k].v=-w1[j][k].v;

			d=d*wn;

		}

	}

	son[0]=n+1;solve(1,n,0);

	rep(1,n,i)put_(ans[i]);

	return 0;

}

5.15 省选模拟赛 T1 点分治 FFT的相关教程结束。