首页 > 代码库 > hdu5909 Tree Cutting
hdu5909 Tree Cutting
假定1为本树的根，对于任意的一个联通子图，可以认为是从树上一个点向子树的儿子节点延伸产生的树。
从而考虑dp:
$f(x,j)$ 表示从x点向子树延伸而出异或和为j的连通子图的个数
考虑从 $f(p,j)$ 转移到 $f(x,j)$
用类似背包的方法：$h(i,j)$ 表示考虑前i个儿子从点x向下延伸产生的异或和为j的连通子图个数，从而有
$$h(i,j) = \sum_{k} h(i-1,k)*f(p,j \oplus k)$$
即 $h(i) = h(i-1) \oplus f(p) $
用fwt变换$O(nlogn)$实现异或卷积。fwt原理见Picks博客。
PS：
***判定叶子节点时发生了问题（我的判定是建双向边后当一个点出度为1时认为其为叶子，可实际上也有可能为根节点）***
以后在判定叶子节点时乖乖judge一下时候是否有儿子。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 5 #define P 1000000007 6 #define N 2010 7 #define M (1<<12) 8 #define LL long long 9 10 using namespace std; 11 12 struct edge{ 13 int x,to; 14 }E[N<<1]; 15 16 int n,m,totE,g[N],f[N][M]; 17 18 void ade(int x,int y){ 19 E[++totE]=(edge){y,g[x]}; g[x]=totE; 20 E[++totE]=(edge){x,g[y]}; g[y]=totE; 21 } 22 23 int add(int a,int b){ 24 if(a+b>=P) return a+b-P; 25 return a+b; 26 } 27 28 int mul(int a,int b){ 29 return (int)((LL)a*(LL)b%(LL)P); 30 } 31 32 int qpow(int x,int n){ 33 int ans=1; 34 for(;n;n>>=1,x=mul(x,x)) if(n&1) ans=mul(ans,x); 35 return ans; 36 } 37 38 int inv2 = qpow(2,P-2); 39 40 // tf(A) = tf(tf(A0)-tf(A1) , tf(A0)+tf(A1) ) 41 void fwt(int a[],int l,int r){ 42 if(l==r) return; 43 int mid=(l+r)>>1,len=(r-l+1)/2; 44 fwt(a,l,mid); 45 fwt(a,mid+1,r); 46 for(int i=l;i<=mid;i++){ 47 int A0 = a[i],A1 = a[i+len]; 48 a[i] = add(A0, P-A1); 49 a[i+len] = add(A0, A1); 50 } 51 } 52 53 //utf(A) = utf(utf((A0+A1)/2) , utf((A1-A0)/2)) 54 void ufwt(int a[],int l,int r){ 55 if(l==r) return; 56 int mid=(l+r)>>1,len=(r-l+1)/2; 57 for(int i=l;i<=mid;i++){ 58 int A0 = a[i],A1 = a[i+len]; 59 a[i] = mul(add(A0, A1),inv2); 60 a[i+len] = mul(add(P-A0, A1),inv2); 61 } 62 ufwt(a,l,mid); 63 ufwt(a,mid+1,r); 64 } 65 66 #define p E[i].x 67 68 int ans[M],h[M],a[N]; 69 70 void dp(int x,int fa){ 71 if(!E[g[x]].to && fa){ 72 f[x][a[x]]=1; 73 ans[a[x]]++; 74 return; 75 } 76 for(int i=g[x];i;i=E[i].to) 77 if(p!=fa) dp(p,x); 78 h[a[x]]=1; 79 fwt(h,0,m-1); 80 for(int i=g[x];i;i=E[i].to) 81 if(p!=fa){ 82 f[p][0]=add(f[p][0],1); 83 fwt(f[p],0,m-1); 84 for(int j=0;j<m;j++) h[j]=mul(h[j],f[p][j]); 85 } 86 ufwt(h,0,m-1); 87 for(int i=0;i<m;i++){ 88 f[x][i]=h[i]; 89 ans[i] = add(ans[i],h[i]); 90 h[i]=0; 91 } 92 } 93 94 int main(){ 95 // freopen("C.txt","r",stdin); 96 int T; 97 scanf("%d",&T); 98 while(T--){ 99 memset(ans,0,sizeof(ans));100 memset(f,0,sizeof(f));101 memset(g,0,sizeof(g));102 totE=0;103 scanf("%d%d",&n,&m);104 for(int i=1;i<=n;i++) scanf("%d",&a[i]);105 for(int i=1,x,y;i<n;i++){106 scanf("%d%d",&x,&y);107 ade(x,y);108 }109 dp(1,0);110 for(int i=0;i<m;i++)111 printf("%d%c",ans[i],i==m-1? ‘\n‘:‘ ‘);112 }113 return 0;114 }
hdu5909 Tree Cutting
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。