2 Oct 2016

HDU5909 Tree Cutting FWT+dp

题目大意:

有一棵$n$个点的无根树，节点依次编号为$1$到$n$，其中节点$i$的权值为$v_i$。

定义一棵树的价值为它所有点的权值的异或和。

现在对于每个$[0,m)$的整数$k$，请统计有多少$T$的非空连通子树的价值等于$k$。

一棵树$T$的连通子树就是它的一个连通子图，并且这个图也是一棵树。


题解:

这种FWT的裸题真是见一道少一道啊。。

$f[i][j]$表示以$i$为根的子树，可以到达的权值为$j$的联通块有多少个

然后转移是一个FWT形式的东西，用FWT优化即可

大爷也是会敲FWT的人啦!

orz KyleYoung ShinFeb LIN452等树分治随手屠的人


Code

#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long ll;
int n,m;
#define bug(x) cout<<#x<<"="<<x<<" "
#define debug(x) cout<<#x<<"="<<x<<endl
inline void rd(int &a){
	a=0;char c;
	while(c=getchar(),!isdigit(c));
	do a=a*10+(c^48);
		while(c=getchar(),isdigit(c));
}
const int M=1e3+50;
const int P=1e9+7;
inline void Mod_add(int &a,int b){
	if((a+=b)>=P)a-=P;
}
struct Edge{
	int to,nxt;
}G[M<<1];
int head[M],tot_edge;
inline void add_edge(int from,int to){
	G[tot_edge]=(Edge){to,head[from]};
	head[from]=tot_edge++;
	G[tot_edge]=(Edge){from,head[to]};
	head[to]=tot_edge++;
}
int f[M][M],inv,res[M];
inline int Mod_Pow(int x,int a){
	int res=1;
	for(;a;a>>=1,x=(ll)x*x%P)
		if(a&1)res=(ll)x*res%P;
	return res;
}
inline void fwt(int *res,int sg){
	for(int s=m;s!=1;s>>=1){
		for(int i=0;i<m;i+=s){
			for(int j=0;j<s>>1;++j){
				int a=res[i+j],b=res[i+j+(s>>1)];
				res[i+j]=(ll)(a+b)*sg%P,res[i+j+(s>>1)]=(ll)(a-b+P)*sg%P;
			}
		}
	}
}
int A[M],C[M];
inline void FWT(int *A,int *B){
	fwt(A,1);
	for(int i=0;i<m;++i)
		A[i]=(ll)A[i]*B[i]%P;
	fwt(A,inv);
}
inline void dfs(int v,int fa=0){
	f[v][A[v]]=1;
	for(int i=head[v];~i;i=G[i].nxt){
		int to=G[i].to;
		if(to==fa)continue;
		dfs(to,v);
		for(int j=0;j<m;++j)C[j]=f[v][j];
		FWT(C,f[to]);
		for(int j=0;j<m;++j)
			Mod_add(f[v][j],C[j]);
	}
	for(int i=0;i<m;++i)
		Mod_add(res[i],f[v][i]);
	fwt(f[v],1);
}
inline void Init(){
	for(int i=0;i<m;++i)res[i]=0;
	tot_edge=0;
	for(int i=1;i<=n;++i){
		head[i]=-1;
		for(int j=0;j<m;++j)f[i][j]=0;
	}
}
inline void nt(int x){
	if(!x)return;
	nt(x/10);putchar(x%10+48);
}
inline void pt(int x){
	if(!x)putchar('0');
	else nt(x);
}
inline void gao(){
	cin>>n>>m;
	Init();
	for(int i=1;i<=n;++i)rd(A[i]);
	for(int i=1,a,b;i<n;++i)
		rd(a),rd(b),add_edge(a,b);
	dfs(1);
	for(int i=0;i<m-1;++i)
		pt(res[i]),putchar(' ');
	pt(res[m-1]),putchar('\n');
}
int main(){
	int _;
	inv=Mod_Pow(2,P-2);
	for(cin>>_;_--;)gao();
	return 0;
}
Tags:
Stats:
comments


Share:


Comments: