題目描述

When God made the first man, he put him on a beautiful garden, the Garden of Eden. Here Adam lived with all animals. God gave Adam eternal life. But Adam was lonely in the garden, so God made Eve. When Adam was asleep one night, God took a rib from him and made Eve beside him. God said to them, “here in the Garden, you can do everything, but you cannot eat apples from the tree of knowledge.”
One day, Satan came to the garden. He changed into a snake and went to live in the tree of knowledge. When Eve came near the tree someday, the snake called her. He gave her an apple and persuaded her to eat it. Eve took a bite, and then she took the apple to Adam. And Adam ate it, too. Finally, they were driven out by God and began a hard journey of life.
The above is the story we are familiar with. But we imagine that Satan love knowledge more than doing bad things. In Garden of Eden, the tree of knowledge has n apples, and there are k varieties of apples on the tree. Satan wants to eat all kinds of apple to gets all kinds of knowledge.So he chooses a starting point in the tree,and starts walking along the edges of tree,and finally stops at a point in the tree(starting point and end point may be same).The same point can only be passed once.He wants to know how many different kinds of schemes he can choose to eat all kinds of apple. Two schemes are different when their starting points are different or ending points are different.
Input
There are several cases.Process till end of input.
For each case, the first line contains two integers n and k, denoting the number of apples on the tree and number of kinds of apple on the tree respectively.
The second line contains n integers meaning the type of the i-th apple. Types are represented by integers between 1 and k .
Each of the following n-1 lines contains two integers u and v,meaning there is one edge between u and v.1≤n≤50000, 1≤k≤10
Output
For each case output your answer on a single line.
Sample Input
3 2
1 2 2
1 2
1 3
Sample Output
6

題目分析

雞凍，終于自己完全獨(dú)立地完成了一道樹分治的題目啦。雖然還是調(diào)了三四個(gè)小時(shí)。。。

題目要求的是訪問所有顏色的樹上節(jié)點(diǎn)的方案數(shù)，而且必須是最短路徑（不能重復(fù)訪問節(jié)點(diǎn)保證的），因此我們聯(lián)想到樹分治。

不同于常見的樹分治都是求樹上路徑如何，這里要求的是路徑上點(diǎn)的狀態(tài)要滿足的條件。為了將問題轉(zhuǎn)化我們將點(diǎn)的狀態(tài)放在路徑上，然后轉(zhuǎn)化成樹分治進(jìn)行解決?，F(xiàn)在問題轉(zhuǎn)化成了如何表示樹的狀態(tài)。發(fā)現(xiàn)節(jié)點(diǎn)的顏色很少，我們可以用狀態(tài)壓縮，將顏色轉(zhuǎn)化成二進(jìn)制的位數(shù)，顏色為x，則對應(yīng)的狀態(tài)就是1<<(x-1)，轉(zhuǎn)化成數(shù)字一來方便表示，二來方便進(jìn)行操作。

我們成功得到重心到所有點(diǎn)的狀態(tài)后如何求滿足條件的點(diǎn)對數(shù)呢？所謂滿足條件，就是兩個(gè)點(diǎn)所表示的狀態(tài)進(jìn)行位操作的或運(yùn)算以后等于(1<<k)-1。

那么我們?nèi)绾慰焖俚玫饺我鈨蓚€(gè)點(diǎn)或運(yùn)算以后等于(1<<k)-1的狀態(tài)數(shù)呢？顯然不能直接進(jìn)行暴力。我們需要聯(lián)想到FWT。

將每個(gè)狀態(tài)數(shù)的點(diǎn)數(shù)存放在狀態(tài)數(shù)組中，然后再對這個(gè)數(shù)組進(jìn)行FWT，則Cnt[(1<<k)-1]中保存的就是答案。

其他的操作就是樹分治的基本操作。

經(jīng)驗(yàn)總結(jié)

雖然很快想到了思路，并且寫出了代碼，而且也可以通過樣例，但是不知道為什么一直WA，而且很不自信，覺得自己寫的思路可能有問題。在網(wǎng)上看其他人的代碼他們好像都沒有用到FWT，好像都是樹形DP什么的，那個(gè)我還不會。但是又覺得自己的應(yīng)該沒有什么大問題。就很絕望。

睡了一晚起來再慢慢調(diào)試，一步一步地看，終于發(fā)現(xiàn)自己在一個(gè)很細(xì)小的地方犯了一個(gè)錯(cuò)誤，雖然不知道為什么自己捏的各種各樣的樣例都能過，但是這個(gè)錯(cuò)誤很根本。改了以后就過啦。

人吶，還是要自信一點(diǎn)，不要遇到錯(cuò)誤就著急看別人怎么樣。

AC代碼

#include<iostream> #include<cstring> #include<cstdio> #include<climits> #include<algorithm> #include<ctime> #include<cstdlib> #include<queue> #include<set> #include<map> #include<cmath>using namespace std; typedef long long ll; const int MAXN=5e4+5; struct edge {int to,last; }Edge[MAXN<<2]; int Last[MAXN],tot; int n,kk,SonNum[MAXN],MaxNum[MAXN],Vis[MAXN],Record[MAXN],Color[MAXN]; int root,rootx,dlen,ss,len; ll ans,Cnt[(1<<11)+100]; int Power[15];void FWT(ll *a,int N,int opt) {for(int i=1;i<N;i<<=1)for(int p=i<<1,j=0;j<N;j+=p)for(int k=0;k<i;++k)/*or*/if(opt==1)a[i+j+k]=(a[j+k]+a[i+j+k]);else a[i+j+k]=(a[i+j+k]-a[j+k]);/*andif(opt==1)a[j+k]=(a[j+k]+a[i+j+k])%MOD;else a[j+k]=(a[j+k]+MOD-a[i+j+k])%MOD;*//*xor{int X=a[j+k],Y=a[i+j+k];a[j+k]=(X+Y)%MOD;a[i+j+k]=(X+MOD-Y)%MOD;//如果不是在模意義下的話，開一個(gè)long long，然后把逆元變成直接除二就好了if(opt==-1)a[j+k]=1ll*a[j+k]*inv%MOD,a[i+j+k]=1ll*a[i+j+k]*inv%MOD;}*/ }int getint() {int x=0,sign=1; char c=getchar();while(c<'0' || c>'9'){if(c=='-') sign=-1; c=getchar();}while(c>='0' && c<='9'){x=x*10+c-'0'; c=getchar();}return x*sign; }void Init() {for(int i=0;i<=n;++i) Last[i]=0,Vis[i]=false;tot=0; }void AddEdge(int u,int v) {Edge[++tot].to=v; Edge[tot].last=Last[u]; Last[u]=tot; }void Read() {for(int i=1;i<=n;++i) Color[i]=getint()-1;int u,v,w;for(int i=1;i<n;i++){u=getint(); v=getint();AddEdge(u,v); AddEdge(v,u);} }void GetRoot(int x,int father) {int v;SonNum[x]=1; MaxNum[x]=1;for(int i=Last[x];i;i=Edge[i].last){v=Edge[i].to; if(v==father || Vis[v]) continue;GetRoot(v,x);SonNum[x]+=SonNum[v];if(SonNum[v]>MaxNum[x]) MaxNum[x]=SonNum[x];}MaxNum[x]=max(MaxNum[x],ss-SonNum[x]);if(rootx>MaxNum[x]) root=x,rootx=MaxNum[x]; }int Deal(int x,int now) {return now|Power[Color[x]]; }void GetDis(int x,int father,int now) {int t;t=Record[++dlen]=Deal(x,now);int v;for(int i=Last[x];i;i=Edge[i].last){v=Edge[i].to; if(v==father|| Vis[v]) continue;GetDis(v,x,t);} }ll Count(int x,int now) {for(int i=0;i<=dlen;++i) Record[i]=0;dlen=0;GetDis(x,0,now);memset(Cnt,0,sizeof(Cnt));for(int i=1;i<=dlen;++i)++Cnt[Record[i]];FWT(Cnt,len,1);for(int i=0;i<len;++i) Cnt[i]=Cnt[i]*Cnt[i];FWT(Cnt,len,-1);ll ret=Cnt[len-1];return ret; }void Solve(int x) {int v;ans+=Count(x,0);Vis[x]=true;for(int i=Last[x];i;i=Edge[i].last){v=Edge[i].to; if(Vis[v]) continue;ans-=Count(v,Deal(x,0));ss=SonNum[v]; rootx=INT_MAX; root=0;GetRoot(v,x);Solve(root);} }void Work() {if(kk==1) return;rootx=INT_MAX; ss=n; root=0; ans=0;len=1<<kk;GetRoot(1,0); Solve(root); }void Write() {if(kk==1) printf("%lld\n",(ll)n*n);else printf("%lld\n",ans); }int main() {for(int i=0;i<15;i++) Power[i]=1<<i;while(~scanf("%d%d",&n,&kk)){Init();Read();Work();Write();}return 0; } 創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅(jiān)持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結(jié)

以上是生活随笔為你收集整理的HDU5977-Garden of Eden-树分治+FWT的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。