HDU5977 Garden of Eden 【FMT】【树形DP】

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题目大意：求有所有颜色的路径数。

题目分析：
参考codeforces997C，先利用基的FMT的性质在$O(2^k)$做FMT，再利用只还原一位的特点在$O(2^k)$还原，不知道为什么网上都要点分治。

代码：

#include<bits/stdc++.h>
#define R register
using namespace std; const int maxn = ; int n,k,a[maxn],fa[maxn],cnt[maxn],head[maxn];
struct edge{int to,nxt;}edges[maxn];
long long f[maxn],pt[maxn]; void read(){
for(R int i=;i<=n;i++) pt[i] = head[i] = ;
for(R int i=;i<=n;i++) scanf("%d",&a[i]),a[i]--;
for(R int i=;i<n;i++){
int u,v; scanf("%d%d",&u,&v);
if(u > v) swap(u,v);
fa[v] = u; edges[i] = (edge){v,head[u]}; head[u] = i;
}
} int dr;
void dfs(int now){
long long tot = ;long long dz = ;
for(R int i=head[now];i;i=edges[i].nxt){
int to = edges[i].to;
dfs(to); dz += tot*f[to]; tot += f[to];
}
dz *= f[now]; dz += f[now]*tot; f[now] = (tot+)*f[now];
pt[now] += dr*dz;
} void work(){
for(R int i=;i<(<<k);i++){
for(R int j=;j<=n;j++) f[j] = ((<<a[j])&i)?:;
dr = ((k-cnt[i])&)?-:;
dfs();
}
long long ans = ;
for(R int i=;i<=n;i++) ans += pt[i];
ans*=; ans += n*(k==);
printf("%lld\n",ans);
} int main(){
for(R int i=;i<=;i++) cnt[i] = cnt[i>>]+(i&);
while(scanf("%d%d",&n,&k) == ){ read(); work(); }
return ;
}