description
solution
点分治枚举路径板板题。。
void getroot(int u,int fa){
sz[u]=1;f[u]=0;
for(RG int i=head[u];i;i=nxt[i]){
RG int v=to[i];if(v==fa||vis[v])continue;
getroot(v,u);sz[u]+=sz[v];
f[u]=max(f[u],sz[v]);
}
f[u]=max(f[u],sum-sz[u]);
if(f[u]<f[root])root=u;
}
void solve(int u){
...
vis[u]=1;
for(RG int i=head[u];i;i=nxt[i]){
RG int v=to[i];if(vis[v])continue;
calc(u,v);sum=sz[v];root=0;
getroot(v,0);
solve(root);
}
}
int main()
{
...
f[0]=sum=n;root=0;
getroot(1,0);
solve(root);
...
}
还要用到一个高维前缀和的玩意儿
//这里是求超集的前前缀和
for(RG int w=0;w<k;w++)//枚举位数
for(RG int i=0;i<(1<<k);i++)//枚举每一个二进制位
if(!(i&(1<<w)))ss[i]+=ss[i|(1<<w)];
code
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<iomanip>
#include<cstdio>
#include<string>
#include<bitset>
#include<cctype>
#include<cmath>
#include<queue>
#include<stack>
#include<ctime>
#define RG register
using namespace std;
const int N=50010;
typedef long long ll;
typedef double dd;
inline int read(){
RG int data=0,w=1;RG char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch<='9'&&ch>='0')data=data*10+ch-48,ch=getchar();
return data*w;
}
void file(){
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
}
int n,k,root,sum,s[N],d[N];ll ans;
int head[N],nxt[N<<1],to[N<<1],val[N<<1],cnt;
void add(int u,int v){
to[++cnt]=v;
nxt[cnt]=head[u];
head[u]=cnt;
}
int sz[N],dep[N],f[N];bool vis[N];
ll tot[20][1<<10],t[1<<10],ss[1<<10];
void getdeep(int u,int fa){
t[dep[u]]++;
for(RG int i=head[u];i;i=nxt[i]){
RG int v=to[i];if(v==fa||vis[v])continue;
dep[v]=dep[u]|(1<<(s[v])-1);getdeep(v,u);
}
}
void calc(int u,int v){
dep[v]=(1<<(s[u]-1))|(1<<(s[v]-1));
for(RG int i=0;i<(1<<k);i++)t[i]=0;
getdeep(v,0);
for(RG int i=0;i<(1<<k);i++)ss[i]=t[i];
for(RG int w=0;w<k;w++)
for(RG int i=0;i<(1<<k);i++)
if(!(i&(1<<w)))
ss[i]+=ss[i|(1<<w)];
for(RG int i=0;i<(1<<k);i++)ans+=2ll*tot[d[u]][i]*ss[((1<<k)-1)^i];
for(RG int i=0;i<(1<<k);i++)tot[d[u]][i]+=t[i];
}
void getroot(int u,int fa){
sz[u]=1;f[u]=0;
for(RG int i=head[u];i;i=nxt[i]){
RG int v=to[i];if(v==fa||vis[v])continue;
getroot(v,u);sz[u]+=sz[v];
f[u]=max(f[u],sz[v]);
}
f[u]=max(f[u],sum-sz[u]);
if(f[u]<f[root])root=u;
}
void solve(int u){
memset(tot[d[u]],0,sizeof(tot[d[u]]));
if(k==1)ans++;tot[d[u]][(1<<(s[u]-1))]++;vis[u]=1;
for(RG int i=head[u];i;i=nxt[i]){
RG int v=to[i];if(vis[v])continue;
calc(u,v);
sum=sz[v];root=0;
getroot(v,0);
d[root]=d[u]+1;
solve(root);
}
}
int main()
{
while(scanf("%d%d",&n,&k)!=EOF){
memset(head,0,sizeof(head));cnt=ans=0;
memset(vis,0,sizeof(vis));
for(RG int i=1;i<=n;i++)s[i]=read();
for(RG int i=1,u,v,w;i<n;i++){
u=read();v=read();add(u,v);add(v,u);
}
f[0]=sum=n;root=0;
getroot(1,0);
d[root]=1;
solve(root);
printf("%lld
",ans);
}
return 0;
}