Garden of Eden
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Problem Description
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.
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
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
分析：考虑树分治；
那么对于当前根，我们dfs得到一个位或集合；
那么我们要求位或值全1的点对数；
那么枚举其中一个点a后,我们要知道b的数目，c[a]|c[b]=(1<<m)-1，c[a]表示从当前根到a的位或值；
不难发现这是高维前缀和；
代码：
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <algorithm> #include <climits> #include <cstring> #include <string> #include <set> #include <bitset> #include <map> #include <queue> #include <stack> #include <vector> #include <cassert> #include <ctime> #define rep(i,m,n) for(i=m;i<=(int)n;i++) #define inf 0x3f3f3f3f #define mod 998244353 #define vi vector<int> #define pb push_back #define mp make_pair #define fi first #define se second #define ll long long #define pi acos(-1.0) #define pii pair<int,int> #define sys system("pause") #define ls (rt<<1) #define rs (rt<<1|1) #define all(x) x.begin(),x.end() const int maxn=1e5+10; const int N=4e5+10; using namespace std; ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);} ll qmul(ll p,ll q,ll mo){ll f=0;while(q){if(q&1)f=(f+p)%mo;p=(p+p)%mo;q>>=1;}return f;} ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p%mod;p=p*p%mod;q>>=1;}return f;} int n,m,k,t,c[maxn],p[maxn],son[maxn],sz,root,bit[1<<10],q[maxn],tmp[1<<10]; ll ans; bool vis[maxn]; vi e[maxn]; void getroot(int x,int y) { int i; son[x]=1;p[x]=0; rep(i,0,e[x].size()-1) { int z=e[x][i]; if(z==y||vis[z])continue; getroot(z,x); son[x]+=son[z]; p[x]=max(p[x],son[z]); } p[x]=max(p[x],sz-son[x]); if(p[x]<p[root])root=x; } void getbit(int x,int y) { q[x]|=(1<<c[x]); bit[q[x]]++; int i; rep(i,0,e[x].size()-1) { int z=e[x][i]; if(z==y||vis[z])continue; q[z]=q[x]; getbit(z,x); } } ll cal(int x,int &p)//计算集合中位或为(1<<m)-1的对数; { memset(bit,0,sizeof(bit)); getbit(x,0); memcpy(tmp,bit,sizeof(bit)); int i,j; rep(i,0,m-1) { rep(j,0,(1<<m)-1) { if(j>>i&1)continue; tmp[j]+=tmp[j^(1<<i)]; } } ll ret=0; rep(i,0,(1<<m)-1)ret+=(ll)bit[i]*tmp[i^((1<<m)-1)]; return ret; } void gao(int x) { int i; q[x]=0; ans+=cal(x,q[x]); vis[x]=true; rep(i,0,e[x].size()-1) { int y=e[x][i]; if(!vis[y]) { q[y]=(1<<c[x]); ans-=cal(y,q[y]); p[0]=sz=son[y]; getroot(y,root=0); gao(root); } } } int main(){ int i,j; while(~scanf("%d%d",&n,&m)) { ans=0; rep(i,1,n) { scanf("%d",&c[i]); c[i]--; e[i].clear(); vis[i]=false; } rep(i,1,n-1) { int x,y; scanf("%d%d",&x,&y); e[x].pb(y);e[y].pb(x); } p[0]=sz=n; getroot(1,root=0); gao(root); printf("%lld ",ans); } return 0; }