HDU5909 Tree Cutting（FWT）

HDU5909 Tree Cutting

题目大意

有一棵有$n$个点的树$T$，每个节点有一个权值$v_i$。定义一棵树的权值为其所有节点的权值的异或和。对于每个数$k\in [0,m)$，求这棵树$T$的权值为$k$的子树的个数。

$T$的子树是$T$的子图，也是一棵树。

输出答案对$10^9+7$取模后的值。

有$T$组数据。

数据范围

$1\le T\le 10,1\le n\le 1000,1\le m\le 2^{10},0\le v_i<m$

题解

前置知识：快速沃尔什变换（$FWT$）

考虑DP。设$f_{i,j}$表示在包含$i$的子树中，权值为$j$的子树。

那么，遍历这棵树，对于$u$的每一个儿子$v$，有转移式

$$f_{u,k}=\sum _{i\oplus j=k}{f}_{u,i}\times f_{v,j}$$

注意每次转移到时候，儿子$v$的DP值$f_{v,0}$要加1，代表儿子$v$及以下的部分不选。

这就可以用$FWT$的异或卷积来做了。

最后统计答案的时候，记得要把每个$f_{i,0}$上多加点1减去。那么，权值为$k$的子树的个数为

$$an{s}_k=\sum _{i=1}^n{f}_k$$

时间复杂度为$O(Tnm\log m)$。

code

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
int t,n,m,tot,d[2005],l[2005],r[2005];
int ans[1<<10],f[1005][1<<10];
const int mod=1000000007,ny2=500000004;
int in(){
	int re=0;
	char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9'){
		re=re*10+ch-'0';
		ch=getchar();
	}
	return re;
}
void add(int xx,int yy){
	l[++tot]=r[xx];d[tot]=yy;r[xx]=tot;
}
void fwt(int *w,int fl){
	for(int s=2;s<=m;s<<=1){
		int mid=s>>1;
		for(int v=0;v<m;v+=s){
			for(int i=0;i<mid;i++){
				int t1=w[v+i],t2=w[v+mid+i];
				w[v+i]=1ll*(t1+t2)%mod;w[v+mid+i]=1ll*(t1-t2+mod)%mod;
				if(fl==-1){
					w[v+i]=1ll*w[v+i]*ny2%mod;
					w[v+mid+i]=1ll*w[v+mid+i]*ny2%mod;
				}
			}
		}
	}
}
void dfs(int u,int fa){
	fwt(f[u],1);
	for(int i=r[u];i;i=l[i]){
		if(d[i]==fa) continue;
		dfs(d[i],u);
		for(int j=0;j<m;j++) f[u][j]=1ll*f[u][j]*f[d[i]][j]%mod;
	}
	fwt(f[u],-1);
	f[u][0]=(f[u][0]+1)%mod;
	fwt(f[u],1);
}
int main()
{
	t=in();
	while(t--){
		n=in();m=in();
		for(int i=1;i<=n;i++){
			++f[i][in()];
		}
		tot=0;
		for(int i=1,x,y;i<n;i++){
			x=in();y=in();
			add(x,y);add(y,x);
		}
		dfs(1,0);
		for(int i=1;i<=n;i++){
			fwt(f[i],-1);
			f[i][0]=(f[i][0]-1+mod)%mod;
		}
		for(int i=1;i<=n;i++){
			for(int j=0;j<m;j++){
				ans[j]=(ans[j]+f[i][j])%mod;
			}
		}
		for(int i=0;i<m;i++){
			printf("%d",ans[i]);
			if(i<m-1) printf(" ");
		}
		printf("\n");
		for(int i=1;i<=n;i++) r[i]=0;
		for(int i=0;i<m;i++) ans[i]=0;
		for(int i=1;i<=n;i++){
			for(int j=0;j<m;j++){
				f[i][j]=0;
			}
		}
	}
	return 0;
}