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

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

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

代码：

1 #include<bits/stdc++.h> 2 #define R register 3 using namespace std; 4 5 const int maxn = 50200; 6 7 int n,k,a[maxn],fa[maxn],cnt[maxn],head[maxn]; 8 struct edge{int to,nxt;}edges[maxn]; 9 long long f[maxn],pt[maxn]; 10 11 void read(){ 12 for(R int i=1;i<=n;i++) pt[i] = head[i] = 0; 13 for(R int i=1;i<=n;i++) scanf("%d",&a[i]),a[i]--; 14 for(R int i=1;i<n;i++){ 15 int u,v; scanf("%d%d",&u,&v); 16 if(u > v) swap(u,v); 17 fa[v] = u; edges[i] = (edge){v,head[u]}; head[u] = i; 18 } 19 } 20 21 int dr; 22 void dfs(int now){ 23 long long tot = 0;long long dz = 0; 24 for(R int i=head[now];i;i=edges[i].nxt){ 25 int to = edges[i].to; 26 dfs(to); dz += tot*f[to]; tot += f[to]; 27 } 28 dz *= f[now]; dz += f[now]*tot; f[now] = (tot+1)*f[now]; 29 pt[now] += dr*dz; 30 } 31 32 void work(){ 33 for(R int i=0;i<(1<<k);i++){ 34 for(R int j=1;j<=n;j++) f[j] = ((1<<a[j])&i)?1:0; 35 dr = ((k-cnt[i])&1)?-1:1; 36 dfs(1); 37 } 38 long long ans = 0; 39 for(R int i=1;i<=n;i++) ans += pt[i]; 40 ans*=2; ans += n*(k==1); 41 printf("%lld\n",ans); 42 } 43 44 int main(){ 45 for(R int i=1;i<=50000;i++) cnt[i] = cnt[i>>1]+(i&1); 46 while(scanf("%d%d",&n,&k) == 2){ read(); work(); } 47 return 0; 48 }

 

转载于:https://www.cnblogs.com/Menhera/p/9514412.html

总结

以上是生活随笔为你收集整理的HDU5977 Garden of Eden 【FMT】【树形DP】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。